結果
| 問題 |
No.529 帰省ラッシュ
|
| コンテスト | |
| ユーザー |
 tempura_pp
|
| 提出日時 | 2018-08-14 03:45:00 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,489 bytes |
| コンパイル時間 | 1,668 ms |
| コンパイル使用メモリ | 125,876 KB |
| 実行使用メモリ | 57,260 KB |
| 最終ジャッジ日時 | 2024-09-24 08:34:36 |
| 合計ジャッジ時間 | 11,270 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 4 WA * 14 |
ソースコード
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ;
typedef vector<vector<int>> graph;
struct LowLink{
graph v,nv;
vector<int> art,low,ord,idx;
vector <pint> bridge;
LowLink(int n):v(n),ord(n,-1),low(n),idx(n,-1){};
void addedge(int x,int y){
v[x].push_back(y);
v[y].push_back(x);
}
bool isbridge(int x,int y){
if(ord[x]>ord[y])swap(x,y);
return ord[x]<low[y];
}
void dfs(int& count,int from,int x){
ord[x]=count++;
low[x]=ord[x];
bool isart=false;
int cnt=0;
for(auto to:v[x]){
if(to==from)continue;
if(ord[to]==-1){
cnt++;
dfs(count,x,to);
if(isbridge(x,to))bridge.push_back({min(x,to),max(to,x)});
if(from!=-1&&ord[x]<=low[to])isart=true;
low[x]=min(low[x],low[to]);
}
else low[x]=min(low[x],ord[to]);
}
if(from==-1&&cnt>1)isart=true;
if(isart)art.push_back(x);
}
void dfs(){
int count=0;
dfs(count,-1,0);
}
graph build(){
dfs();
int k=0;
idx[0]=k++;
stack<int> st;
st.push(0);
while(!st.empty()){
int x=st.top();st.pop();
for(auto to:v[x]){
if(idx[to]!=-1)continue;
if(isbridge(x, to))idx[to]=k++;
else idx[to]=idx[x];
st.push(to);
}
}
nv.resize(k);
for(pint e:bridge){
nv[idx[e.first]].push_back(idx[e.second]);
nv[idx[e.second]].push_back(idx[e.first]);
}
return nv;
}
};
struct SegmentTree{
private:
int n;
vector<ll> node;
public:
SegmentTree(int sz,ll init){
n=1;
while(n<sz)n*=2;
node.resize(2*n-1,init);
}
void update(int k,ll x){
k+=n-1;
node[k]=x;
while(k>0){
k=(k-1)/2;
node[k]=max(node[2*k+1],node[2*k+2]);
}
}
//[a,b)でのminを返す
ll get(int a,int b,int k=0,int l=0,int r=-1){
if(r<0)r=n;
if(r<=a||b<=l)return -1;
if(a<=l&&r<=b)return node[k];
ll xl=get(a,b,2*k+1,l,(l+r)/2);
ll xr=get(a,b,2*k+2,(l+r)/2,r);
return max(xl,xr);
}
};
SegmentTree sg(101010,-1);
struct HLDecomposition{
int n,pos;
vector<vector<int>> v;
vector<int> idx,head,sz,hvy,par,depth,inv,type;
HLDecomposition(){};
HLDecomposition(int s):
n(s),pos(0),v(n),idx(n,-1),head(n),sz(n,1),
hvy(n,-1),par(n),depth(n),inv(n),type(n){}
HLDecomposition(vector<vector<int>> nv):
n(nv.size()),pos(0),v(nv),idx(n,-1),head(n),sz(n,1),
hvy(n,-1),par(n),depth(n),inv(n),type(n){}
void addedge(int x,int y){
v[x].push_back(y);
v[y].push_back(x);
}
void dfs(int rt){
par[rt]=-1;
depth[rt]=0;
stack<pint> st;
st.push({rt,0});
while(!st.empty()){
int x=st.top().first;
int& i=st.top().second;
if(i<(int)v[x].size()){
int to=v[x][i++];
if(to==par[x])continue;
par[to]=x;
depth[to]=depth[x]+1;
st.push({to,0});
}
else {
st.pop();
int res=0;
for(int to:v[x]){
if(to==par[x])continue;
sz[x]+=sz[to];
if(sz[to]>res)res=sz[to],hvy[x]=to;
}
}
}
}
void bfs(int r,int c){
int &k=pos;
queue<int> q;
q.push(r);
while(!q.empty()){
int h=q.front();q.pop();
for(int x=h;x!=-1;x=hvy[x]){
type[x]=c;
head[x]=h;
idx[x]=k++;
inv[idx[x]]=x;
for(int to:v[x])
if(to!=par[x]&&to!=hvy[x])q.push(to);
}
}
}
void build(vector<int> rs=vector<int>(1,0)){
int c=0;
for(int r:rs){
dfs(r);
bfs(r,c++);
}
}
int f(int x,int y){
//ここに何か書く！！！
return sg.get(x,y+1);
}
int for_v(int x,int y){
int res=-1;
while(1){
if(idx[x]>idx[y])swap(x,y);
res=max(res,f(max(idx[head[y]],idx[x]),idx[y]));
if(head[x]!=head[y])y=par[head[y]];
else break;
}
return res;
}
void for_edge(int x,int y){
while(1){
if(idx[x]>idx[y])swap(x,y);
if(head[x]!=head[y]){
f(idx[head[y]],idx[y]);
y=par[head[y]];
}
else{
if(x!=y)f(idx[x]+1,idx[y]);
break;
}
}
}
int lca(int x,int y){
while(1){
if(idx[x]>idx[y])swap(x,y);
if(head[x]==head[y])return x;
y=par[head[y]];
}
}
int dist(int x,int y){
return depth[x]+depth[y]-2*depth[lca(x,y)];
}
};
int main(){
int n,m,q;
cin>>n>>m>>q;
LowLink ll(n);
rep(i,m){
int x,y;
cin>>x>>y;
x--;y--;
ll.addedge(x, y);
}
vector<vector<int>> nv=ll.build();
HLDecomposition hl(nv);
hl.build();
map<int,int> mp;
priority_queue<int> pq[n];
while(q--){
int c,x,y;
cin>>c>>x>>y;
if(c==1){
x=ll.idx[--x];
mp[y]=x;
pq[x].push(y);
if(pq[x].top()==y)sg.update(x, y);
}
else{
x=ll.idx[--x];
y=ll.idx[--y];
int ret=hl.for_v(x, y);
cout<<ret<<endl;
if(ret==-1)continue;
int id=mp[ret];
pq[id].pop();
if(pq[id].empty())sg.update(id, -1);
else sg.update(id, pq[id].top());
}
}
return 0;
}