結果

問題 No.529 帰省ラッシュ
ユーザー koprickykopricky
提出日時 2017-12-31 09:45:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 511 ms / 4,500 ms
コード長 10,478 bytes
コンパイル時間 2,804 ms
コンパイル使用メモリ 197,432 KB
実行使用メモリ 43,748 KB
最終ジャッジ日時 2024-06-01 09:57:19
合計ジャッジ時間 8,337 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 4 ms
6,940 KB
testcase_05 AC 4 ms
6,944 KB
testcase_06 AC 4 ms
6,940 KB
testcase_07 AC 5 ms
6,944 KB
testcase_08 AC 312 ms
26,496 KB
testcase_09 AC 288 ms
25,804 KB
testcase_10 AC 337 ms
31,008 KB
testcase_11 AC 323 ms
31,248 KB
testcase_12 AC 199 ms
24,960 KB
testcase_13 AC 219 ms
43,748 KB
testcase_14 AC 306 ms
30,848 KB
testcase_15 AC 511 ms
33,244 KB
testcase_16 AC 511 ms
33,248 KB
testcase_17 AC 310 ms
41,012 KB
testcase_18 AC 314 ms
41,380 KB
testcase_19 AC 327 ms
38,660 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:320:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  320 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:324:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  324 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
main.cpp:346:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  346 |         scanf("%d%d%d",&p,&q,&r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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;

struct HLdecomposition{
    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){}
        P Up(){
            return P(parid, pardepth);
        }
    };
    vector<vector<int> > G;
    vector<int> stsize, nxpath;
    vector<int> pathorder, pathid;   //何番目のパスに属するか,そのパスの何番目か
    vector<Centroid> centroids; //パスが格納
    vector<int> index;
    void Buildstsize(){
        stack<P> s;
        s.push(P(0, -1));
        while(!s.empty()) {
            P p = s.top();
            s.pop();
            if(stsize[p.first] != -1){
                nxpath[p.first] = -1;
                for(int to : G[p.first]){
                    //親に向かう場合
                    if(p.second == to){
                        continue;
                    }
                    stsize[p.first] += stsize[to];
                    if(nxpath[p.first] == -1 || stsize[nxpath[p.first]] < stsize[to]) {
                        nxpath[p.first] = to;
                    }
                }
            }else{
                s.push(p);
                stsize[p.first] = 1;
                for(int to : G[p.first]){
                    if(p.second != to){
                        s.push(P(to, p.first));
                    }
                }
            }
        }
    }
    void BuildPath()
    {
        stack<P> s;
        centroids.emplace_back(-1, -1, 0, 0);
        s.push(P(0, -1));
        pathorder[0] = 0;
        while(!s.empty()) {
            P p = s.top();
            s.pop();
            pathid[p.first] = centroids[pathorder[p.first]].sz;
            for(int to : G[p.first]){
                if(p.second == to) continue;
                if(to == nxpath[p.first]){ // Centroid-Pathについて
                    pathorder[to] = pathorder[p.first];
                }else{                      // Centroid-Pathでないものについて
                    pathorder[to] = (int)centroids.size();
                    centroids.emplace_back(pathorder[p.first], pathid[p.first], centroids[pathorder[p.first]].depth + 1,0);
                }
                s.emplace(to, p.first);
            }
            centroids[pathorder[p.first]].sz++;
        }
    }
    void Build_index(){
        int ptr = 0;
        for(auto& centroid : centroids){
            index.push_back(ptr);
            ptr += centroid.sz;
        }
    }
    void add_edge(int x, int y)
    {
        G[x].push_back(y), G[y].push_back(x);
    }
    void build()
    {
        Buildstsize(); BuildPath(), Build_index();
    }
    //idxが何番目のパスの何番目か
    P info(int idx)
    {
        return P(pathorder[idx], pathid[idx]);
    }
    //元の頂点のインデックスの配列上でのidを返す
    int get(int a)
    {
        P p = info(a);
        return (index[p.first] + p.second);
    }
    Centroid &operator[](int k)
    {
        return (centroids[k]);
    }
    void query(int a, int b, const function< void(int, int) > &func)
    {
        int pathidA, pathdepthA, pathidB, pathdepthB;
        tie(pathidA, pathdepthA) = info(a);
        tie(pathidB, pathdepthB) = info(b);
        while(pathidA != pathidB) {
            if(centroids[pathidA].depth > centroids[pathidB].depth) {
                func(index[pathidA], index[pathidA] + pathdepthA + 1);
                tie(pathidA, pathdepthA) = centroids[pathidA].Up();
            }else{
                func(index[pathidB], index[pathidB] + pathdepthB + 1);
                tie(pathidB, pathdepthB) = centroids[pathidB].Up();
            }
        }
        if(pathdepthA > pathdepthB) swap(pathdepthA, pathdepthB);
        func(index[pathidA] + pathdepthA, index[pathidA] + pathdepthB + 1);
    }
    HLdecomposition(){};
    void construct(int node_size)
    {
        G.resize(node_size);
        stsize.assign(node_size, -1);
        nxpath.resize(node_size);
        pathorder.resize(node_size);
        pathid.resize(node_size);
    }
};

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);
            }
        }
    }
}
0