結果
| 問題 |
No.529 帰省ラッシュ
|
| コンテスト | |
| ユーザー |
 kopricky
|
| 提出日時 | 2018-06-09 11:16:26 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,362 bytes |
| コンパイル時間 | 2,133 ms |
| コンパイル使用メモリ | 194,484 KB |
| 実行使用メモリ | 45,156 KB |
| 最終ジャッジ日時 | 2024-06-30 12:26:20 |
| 合計ジャッジ時間 | 8,437 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 8 WA * 10 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:277:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
277 | scanf("%d%d%d",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:281:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
281 | scanf("%d%d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:303:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
303 | scanf("%d%d%d",&p,&q,&r);
| ~~~~~^~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl
using namespace std;
typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;
const int MAX_N = 100005;
class HLdecomposition{
private:
struct Centroid{
int parid, pardepth, depth, sz; //親のパスのid,親のノードは親のパスの何番目,パスの深さ,属する頂点の数
Centroid(int idx, int dep, int deep, int size) : parid(idx), pardepth(dep), depth(deep), sz(size){}
inline P Up(){ return P(parid, pardepth); }
};
int V;
vector<vector<int> > G;
//何番目のパスに属するか,そのパスの何番目か
vector<int> stsize, nxpath, pathorder, pathid, index;
vector<Centroid> centroids; //パスが格納
void BuildStsize(int u, int p){
stsize[u] = 1;
for(int v : G[u]){
if(v == p) continue;
BuildStsize(v, u);
stsize[u] += stsize[v];
if(nxpath[u] == -1 || stsize[v] > stsize[nxpath[u]]){
nxpath[u] = v;
}
}
}
void BuildPath(int u, int p){
pathid[u] = centroids[pathorder[u]].sz - 1;
for(int v : G[u]){
if(v == p) continue;
if(v == nxpath[u]){ // Centroid-Pathについて
pathorder[v] = pathorder[u];
centroids[pathorder[u]].sz++;
}else{ // Centroid-Pathでないものについて
pathorder[v] = (int)centroids.size();
centroids.emplace_back(pathorder[u], pathid[u], centroids[pathorder[u]].depth + 1, 1);
}
BuildPath(v, u);
}
}
void BuildIndex(){
int ptr = 0;
for(auto& centroid : centroids){
index.push_back(ptr);
ptr += centroid.sz;
}
}
public:
void add_edge(int u, int v){
G[u].push_back(v), G[v].push_back(u);
}
void build(){
BuildStsize(0, -1);
BuildPath(0, -1);
BuildIndex();
}
//元の頂点のインデックスの配列上でのidを返す
int get(int a){
return index[pathorder[a]] + pathid[a];
}
void query(int a, int b, const function< void(int, int) > &func){
int pathidA = pathorder[a], pathdepthA = pathid[a];
int pathidB = pathorder[b], pathdepthB = pathid[b];
while(pathidA != pathidB) {
if(centroids[pathidA].depth > centroids[pathidB].depth) {
func(index[pathidA], index[pathidA] + pathdepthA + 1);
pathidA = centroids[pathidA].parid, pathdepthA = centroids[pathidA].pardepth;
}else{
func(index[pathidB], index[pathidB] + pathdepthB + 1);
pathidB = centroids[pathidB].parid, pathdepthB = centroids[pathidB].pardepth;
}
}
if(pathdepthA > pathdepthB) swap(pathdepthA, pathdepthB);
func(index[pathidA] + pathdepthA, index[pathidA] + pathdepthB + 1);
}
void construct(int node_size){
V = node_size;
G.resize(V), stsize.resize(V, -1), nxpath.resize(V, -1), pathorder.resize(V, -1), pathid.resize(V, -1);
pathorder[0] = 0, centroids.emplace_back(-1, -1, 0, 1);
}
};
class biconnected{
public:
vector<vector<int> > G,tree;
vector<int> ord,low,cmp;
vector<vector<P> > check;
vector<P> bridge;
vector<bool> visit;
int V,kind;
biconnected(int node_size){
V = node_size; kind = 0;
G.resize(V);
check.resize(V),ord.resize(V),low.resize(V);
cmp.resize(V),visit.resize(V,false);
}
void build(){
int id = 0;
rep(i,V){
if(!visit[i]){
dfs(i,-1,id);
}
}
}
void dfs(int v,int p,int &k)
{
visit[v] = true;
ord[v] = k++;
low[v] = ord[v];
rep(i,(int)G[v].size()){
int w = G[v][i];
if(!visit[w]){
dfs(w,v,k);
low[v] = min(low[v],low[w]);
if(ord[v] < low[w]){
bridge.pb(P(v,w));
check[v][i].second = 1;
check[w][check[v][i].first].second = 1;
}
//(v,w)は後退辺
}else if(w != p){
low[v] = min(low[v],ord[w]);
}
}
}
void add_edge(int u,int v)
{
G[u].push_back(v),G[v].push_back(u);
check[u].push_back(P((int)check[v].size(),0));
check[v].push_back(P((int)check[u].size()-1,0));
}
void restrict_dfs(int u,int p,int kind,queue<int>& que)
{
visit[u] = true;
cmp[u] = kind;
rep(i,(int)G[u].size()){
int w = G[u][i];
if(check[u][i].second){
if(!visit[w]){
que.push(w);
}
}else if(!visit[w]){
restrict_dfs(w,u,kind,que);
}
}
}
void rebuild()
{
fill(visit.begin(),visit.end(),false);
rep(i,V){
if(!visit[i]){
queue<int> que;
que.push(i);
while(!que.empty()){
int p = que.front();
que.pop();
restrict_dfs(p,-1,kind,que);
kind++;
}
}
}
}
// auxiliary graph を作る
void make_bctree(HLdecomposition& hl)
{
rebuild();
hl.construct(kind);
rep(i,(int)bridge.size()){
hl.add_edge(cmp[bridge[i].first],cmp[bridge[i].second]);
}
}
};
template<typename V> class segtree {
private:
int n,sz;
vector<V> node;
vector<int> node_id;
public:
segtree(vector<V>& v){
sz = (int)v.size();
n = 1;
while(n < sz){
n *= 2;
}
node.resize(2*n-1),node_id.resize(2*n-1);
rep(i,sz){
node[i+n-1] = v[i];
node_id[i+n-1] = i;
}
for(int i=n-2; i>=0; i--){
if(node[2*i+1] > node[2*i+2]){
node[i] = node[2*i+2];
node_id[i] = node_id[2*i+2];
}else{
node[i] = node[2*i+1];
node_id[i] = node_id[2*i+1];
}
}
}
void update(int k,int a)
{
k += n-1;
node[k] = a,node_id[k] = k-(n-1);
while(k>0){
k = (k-1)/2;
if(node[2*k+1] < node[2*k+2]){
node[k] = node[2*k+1],node_id[k] = node_id[2*k+1];
}else{
node[k] = node[2*k+2],node_id[k] = node_id[2*k+2];
}
}
}
pair<V,int> query(int a,int b,int k=0,int l=0,int r=-1)
{
if(r < 0) r = n;
if(r <= a || b <= l){
return pair<V,int>(numeric_limits<V>::max(),-1);
}
if(a <= l && r <= b){
return pair<V,int>(node[k],node_id[k]);
}else{
pair<V,int> vl = query(a,b,2*k+1,l,(l+r)/2);
pair<V,int> vr = query(a,b,2*k+2,(l+r)/2,r);
return min(vl,vr);
}
}
void print()
{
rep(i,sz){
pair<V,int> p;
p = query(i,i+1);
cout << "st[" << i << "]: " << p.fi << " " << p.se << endl;
}
}
};
int main()
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
biconnected bc(n);
rep(i,m){
int u,v;
scanf("%d%d",&u,&v);
bc.add_edge(u-1,v-1);
}
bc.build();
HLdecomposition hl;
bc.make_bctree(hl);
hl.build();
int& kind = bc.kind;
vi& cmp = bc.cmp;
vi u(kind,0);
vector<priority_queue<int> > que(kind);
vector<int> mx(kind,0);
vector<int> trans(kind);
vector<int> unzip(kind);
rep(i,kind){
int res = hl.get(i);
trans[i] = res;
unzip[res] = i;
}
segtree<int> seg(u);
rep(i,q){
int p,q,r;
scanf("%d%d%d",&p,&q,&r);
if(p == 1){
int id = cmp[q-1];
que[id].push(r);
if(mx[id] < r){
mx[id] = r;
seg.update(trans[id],-r);
}
}else{
int id1 = cmp[q-1],id2 = cmp[r-1];
P ans = P(0,-1);
hl.query(id1,id2,[&](int l, int r){ ans = min(ans,seg.query(l, r)); });
if(ans.fi == 0){
printf("-1\n");
}else{
int real_id = unzip[ans.se];
que[real_id].pop();
if(que[real_id].empty()){
seg.update(ans.se,0);
mx[real_id] = 0;
}else{
int res = que[real_id].top();
seg.update(ans.se,-res);
mx[real_id] = res;
}
printf("%d\n", -ans.fi);
}
}
}
}