結果

問題 No.529 帰省ラッシュ
ユーザー PulmnPulmn
提出日時 2018-09-14 21:28:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 648 ms / 4,500 ms
コード長 3,888 bytes
コンパイル時間 2,937 ms
コンパイル使用メモリ 192,128 KB
実行使用メモリ 43,180 KB
最終ジャッジ日時 2023-09-20 11:11:05
合計ジャッジ時間 12,122 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 7 ms
4,380 KB
testcase_05 AC 7 ms
4,380 KB
testcase_06 AC 7 ms
4,380 KB
testcase_07 AC 7 ms
4,376 KB
testcase_08 AC 427 ms
21,200 KB
testcase_09 AC 418 ms
21,680 KB
testcase_10 AC 470 ms
27,316 KB
testcase_11 AC 461 ms
27,520 KB
testcase_12 AC 363 ms
22,216 KB
testcase_13 AC 330 ms
43,180 KB
testcase_14 AC 406 ms
23,760 KB
testcase_15 AC 648 ms
30,384 KB
testcase_16 AC 630 ms
30,256 KB
testcase_17 AC 490 ms
36,748 KB
testcase_18 AC 492 ms
37,152 KB
testcase_19 AC 484 ms
35,088 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

class Segment_Tree{
	private:
	int n;
	vi date;
	int Rec(int a,int b,int k,int l,int r){
		if(r<=a||b<=l) return -1;
		if(a<=l&&r<=b) return date[k];
		int m=(l+r)/2;
		return max(Rec(a,b,k*2+1,l,m),Rec(a,b,k*2+2,m,r));
	}
	public:
	void Init(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vi(2*n-1,-1);
	}
	void Update(int k,int x){
		k+=n-1;
		date[k]=x;
		while(k>0){
			k=(k-1)/2;
			date[k]=max(date[k*2+1],date[k*2+2]);
		}
	}
	int Query(int a,int b){
		return Rec(a,b,0,0,n);
	}
	int Open(int k){
		return date[k+n-1];
	}
};

class Graph{
	private:
	int n;
	vvi g;
	
	vi vid,head,sub,hvy,par,dep,inv;
	Segment_Tree st;
	
	vi imos,big;
	//dep;
	vp edge;
	
	void HLdfs(int rt){
		stack<P> sta;
		sta.push({rt,0});
		while(!sta.empty()){
			P p=sta.top();sta.pop();
			int v=p.first,I=p.second;
			if(I<(int)g[v].size()){
				int u=g[v][I];
				sta.push({v,I+1});
				if(u==par[v]) continue;
				par[u]=v;
				dep[u]=dep[v]+1;
				sta.push({u,0});
			}
			else{
				int M=0;
				sub[v]++;
				for(auto u:g[v]) if(u!=par[v]){
					sub[v]+=sub[u];
					if(M<sub[u]){
						M=sub[u];
						hvy[v]=u;
					}
				}
			}
		}
	}
	void HLbfs(int rt){
		int id=0;
		queue<int> q;
		q.push(rt);
		while(!q.empty()){
			int v=q.front();q.pop();
			for(int u=v;u!=-1;u=hvy[u]){
				vid[u]=id++;
				inv[vid[u]]=u;
				head[u]=v;
				for(auto w:g[u]) if(w!=par[u]&&w!=hvy[u]) q.push(w);
			}
		}
	}
	int Query_vertex(int u,int v){
		int M=-1;
		while(1){
			if(vid[u]>vid[v]) swap(u,v);
			M=max(M,st.Query(max(vid[head[v]],vid[u]),vid[v]+1));
			if(head[u]==head[v]) break;
			v=par[head[v]];
		}
		return M;
	}
	void HL(int v){
		head=sub=par=dep=inv=vi(n);
		vid=hvy=par=vi(n,-1);
		st.Init(n);
		HLdfs(0);HLbfs(0);
	}
	void Bdfs(int v,int d){
		dep[v]=d;
		for(auto u:g[v]) if(dep[u]==-1) Bdfs(u,d+1);
	}
	int BDFS(int v){
		int d=dep[v],S=0;
		for(auto u:g[v]){
			int D=dep[u];
			if(D==d-1) continue;
			if(D==d+1) S+=BDFS(u);
			else if(D<d) S++;
			else S--;
		}
		return imos[v]=S;
	}
	void BDfs(int v,int t,int& id){
		big[v]=t;
		for(auto u:g[v]) if(dep[u]==dep[v]+1){
			if(imos[u]) BDfs(u,t,id);
			else{
				id++;
				BDfs(u,id,id);
			}
		}
	}
	int Biconnect(){
		imos=big=vi(n);
		dep=vi(n,-1);
		int t=0;
		Bdfs(0,0);BDFS(0);BDfs(0,0,t);
		return t+1;
	}
	public:
	Graph(int v){
		n=v;
		g=vvi(v);
	}
	void add_edge(int s,int t){
		g[s].push_back(t);
		g[t].push_back(s);
	}
	void solve(int Q){
		int N=Biconnect();
		Graph G(N);
		for(int u=0;u<n;u++) for(auto v:g[u]) if(big[u]<big[v]) G.add_edge(big[u],big[v]);
		G.HL(0);
		vector<priority_queue<int> > q(N);
		map<int,int> mp;
		for(int i=0;i<N;i++) q[i].push(-1);
		vi ans;
		int tmp=0;
		for(int i=0;i<Q;i++){
			int t,A,B;
			cin>>t>>A>>B;
			A=big[A-1];
			if(t==1){
				q[A].push(B);
				G.st.Update(G.vid[A],q[A].top());
				mp[B]=A;
			}
			else{
				B=big[B-1];
				int res=G.Query_vertex(A,B);
				ans.push_back(res);
				tmp++;
				cout<<res<<endl;
				if(res==-1) continue;
				int v=mp[res];
				q[v].pop();
				G.st.Update(G.vid[v],q[v].top());
			}
		}
	}
};

int n,m,q;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>q;
	Graph g(n);
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		g.add_edge(u-1,v-1);
	}
	g.solve(q);
}
0