結果

問題 No.529 帰省ラッシュ
ユーザー koprickykopricky
提出日時 2019-11-22 03:54:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 220 ms / 4,500 ms
コード長 8,467 bytes
コンパイル時間 2,919 ms
コンパイル使用メモリ 196,040 KB
実行使用メモリ 35,432 KB
最終ジャッジ日時 2024-10-11 02:28:27
合計ジャッジ時間 7,933 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 3 ms
5,248 KB
testcase_08 AC 105 ms
16,384 KB
testcase_09 AC 104 ms
17,152 KB
testcase_10 AC 136 ms
23,744 KB
testcase_11 AC 139 ms
23,944 KB
testcase_12 AC 82 ms
17,536 KB
testcase_13 AC 137 ms
35,432 KB
testcase_14 AC 98 ms
19,200 KB
testcase_15 AC 219 ms
26,856 KB
testcase_16 AC 220 ms
26,860 KB
testcase_17 AC 189 ms
33,304 KB
testcase_18 AC 186 ms
33,560 KB
testcase_19 AC 176 ms
31,732 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#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;

#define getchar getchar_unlocked
#define putchar putchar_unlocked

int in() {
    int n, c;
    while ((c = getchar()) < '0') if (c == EOF) return -1;
    n = c - '0';
    while ((c = getchar()) >= '0') n = n * 10 + c - '0';
    return n;
}

void out(int n) {
    int res[11], i = 0;
    do { res[i++] = n % 10, n /= 10; } while (n);
    while (i) putchar(res[--i] + '0');
    putchar('\n');
}

class HLdecomposition{
public:
    int V;
    vector<vector<int> > G;
    vector<int> stsize, parent, pathtop, in, out;
    void BuildStsize(int u, int p){
        stsize[u] = 1, parent[u] = p;
        for(int& v : G[u]){
            if(v == p) continue;
            BuildStsize(v, u);
            stsize[u] += stsize[v];
            if(stsize[v] > stsize[G[u][0]]){
                swap(v, G[u][0]);
            }
        }
    }
    void BuildPath(int u, int p, int& tm){
        in[u] = tm++;
        for(int v : G[u]){
            if(v == p) continue;
            pathtop[v] = (v == G[u][0] ? pathtop[u] : v);
            BuildPath(v, u, tm);
        }
        out[u] = tm;
    }

public:
    void add_edge(int u, int v){
        G[u].push_back(v), G[v].push_back(u);
    }
    void build(){
        int tm = 0;
        BuildStsize(0, -1), BuildPath(0, -1, tm);
    }
    //元の頂点のインデックスの配列上でのidを返す
    inline int get(int a){
        return in[a];
    }
    int lca(int a, int b){
        int pa = pathtop[a], pb = pathtop[b];
        while(pathtop[a] != pathtop[b]){
            if(in[pa] > in[pb]){
                a = parent[pa], pa = pathtop[a];
            }else{
                b = parent[pb], pb = pathtop[b];
            }
        }
        if(in[a] > in[b]) swap(a, b);
        return a;
    }
    void subtree_query(int a, const function< void(int, int) > &func){
        func(in[a], out[a]);
    }
    void path_query(int a, int b, const function< void(int, int) > &func){
        int pa = pathtop[a], pb = pathtop[b];
        while(pathtop[a] != pathtop[b]){
            if(in[pa] > in[pb]){
                func(in[pa], in[a] + 1);
                a = parent[pa], pa = pathtop[a];
            }else{
                func(in[pb], in[b] + 1);
                b = parent[pb], pb = pathtop[b];
            }
        }
        if(in[a] > in[b]) swap(a, b);
        func(in[a], in[b] + 1);
    }
    void construct(int node_size){
        V = node_size, G.resize(V), stsize.resize(V, 0), parent.resize(V, -1),
            pathtop.resize(V, -1), in.resize(V, -1), out.resize(V, -1);
    }
};

class biconnected {
private:
    void dfs(int u, int p, int& tm)
    {
        bool flag = false;
        ord[u] = low[u] = tm++, st.push(u);
        for(int i = 0; i < (int)G[u].size(); i++){
            int v = G[u][i];
            if(ord[v] < 0){
                dfs(v, u, tm);
                low[u] = min(low[u], low[v]);
            }else if(v != p){
                low[u] = min(low[u], ord[v]);
            }else{
                if(flag) low[u] = min(low[u], ord[v]);
                else flag = true;
            }
        }
        if(ord[u] == low[u]){
            if(p >= 0) bridge.emplace_back(u, p);
            while(true){
                const int v = st.top();
                st.pop();
                cmp[v] = kind;
                if(v == u) break;
            }
            ++kind;
        }
    }

public:
    const int V;
    int kind;
    vector<vector<int> > G, tree;
    vector<pair<int, int> > bridge;
    vector<int> ord, low, cmp;
    stack<int> st;
    biconnected(int node_size)
        : V(node_size), kind(0), G(V), ord(V, -1), low(V), cmp(V){}
    void add_edge(const int u, const int v){
        G[u].push_back(v), G[v].push_back(u);
    }
    // 橋を検出する(二(辺)連結成分の個数を返す).
    int detect_bridge(){
        int tm = 0;
        for(int i = 0; i < V; ++i){
            if(ord[i] < 0) dfs(i, -1, tm);
        }
        for(int i = 0; i < V; ++i) cmp[i] = kind - 1 - cmp[i];
        return kind;
    }
    // 2(辺)連結成分を頂点とする木(tree) を作る(事前に detect_bridge() を呼んでおく必要がある).
    // 木の頂点数を返す.
    // cmp[i] は元の頂点 i の含まれる頂点(2(辺)連結成分) を表す.
    int make_bctree(HLdecomposition& hl)
    {
        hl.construct(kind);
        for(int i = 0; i < (int)bridge.size(); i++){
            int a = cmp[bridge[i].first], b = cmp[bridge[i].second];
            hl.add_edge(a, b);
        }
        return kind;
    }
};

#define T int

class segtree {
private:
    int n,sz;
    vector<pair<T, int> > node;
public:
    segtree(vector<T>& v){
        sz = (int)v.size();
        n = 1;
        while(n < sz){
            n *= 2;
        }
        node.resize(2*n);
        rep(i,sz){
            node[i+n] = make_pair(v[i], i);
        }
        for(int i=n-1; i>=1; i--){
            node[i] = min(node[2*i], node[2*i+1]);
        }
    }
    void update(int k, T a)
    {
    	node[k+=n] = make_pair(a, k);
    	while(k>>=1){
            node[k] = min(node[2*k], node[2*k+1]);
    	}
    }
    pair<T, int> query(int a,int b,int k=0,int l=0,int r=-1)
    {
        pair<T, int> res1 = make_pair(numeric_limits<T>::max(), -1);
        pair<T, int> res2 = make_pair(numeric_limits<T>::max(), -1);
        a += n, b += n;
        while(a != b){
            if(a % 2) cmn(res1, node[a++]);
            if(b % 2) cmn(res2, node[--b]);
            a >>= 1, b>>= 1;
        }
        return min(res1, res2);
    }
    void print()
    {
        rep(i,sz){
            pair<T, int> p;
            p = query(i,i+1);
            cout << "st[" << i << "]: " << p.fi << " " << p.se << endl;
        }
    }
};

int main()
{
    int n,m,q;
    n = in(), m = in(), q = in();
    biconnected bc(n);
    rep(i,m){
        int u = in(), v = in();
        bc.add_edge(u-1,v-1);
    }
    bc.detect_bridge();
    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 seg(u);
    rep(i,q){
        int p,q,r;
        p = in(), q = in(), r = in();
        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.path_query(id1,id2,[&](int l, int r){ ans = min(ans,seg.query(l, r)); });
            if(ans.fi == 0){
                putchar('-'), putchar('1'), putchar('\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;
                }
                out(-ans.fi);
            }
        }
    }
}
0