結果

問題 No.529 帰省ラッシュ
ユーザー tempura_pptempura_pp
提出日時 2018-08-14 14:31:00
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 880 ms / 4,500 ms
コード長 6,532 bytes
コンパイル時間 1,634 ms
コンパイル使用メモリ 126,792 KB
実行使用メモリ 57,260 KB
最終ジャッジ日時 2024-09-24 08:46:21
合計ジャッジ時間 11,788 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,812 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 11 ms
6,940 KB
testcase_05 AC 11 ms
6,940 KB
testcase_06 AC 11 ms
6,944 KB
testcase_07 AC 11 ms
6,940 KB
testcase_08 AC 642 ms
26,188 KB
testcase_09 AC 624 ms
27,072 KB
testcase_10 AC 708 ms
36,352 KB
testcase_11 AC 716 ms
36,860 KB
testcase_12 AC 553 ms
28,180 KB
testcase_13 AC 554 ms
57,260 KB
testcase_14 AC 639 ms
30,080 KB
testcase_15 AC 873 ms
42,268 KB
testcase_16 AC 880 ms
42,148 KB
testcase_17 AC 722 ms
49,572 KB
testcase_18 AC 717 ms
49,960 KB
testcase_19 AC 721 ms
47,068 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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]=0;
       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+1);
       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--;
            x=hl.idx[ll.idx[x]];
            mp[y]=x;
            pq[x].push(y);
            if(pq[x].top()==y)sg.update(x, y);
        }
        else{
            --x;--y;
            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;
}
0