제출 #130356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130356		osaaateiasavtnl	다리 (APIO19_bridges)	C++17	0 / 100	3052 ms	524292 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define app push_back
const int N = 1e5 + 7;
const int INF = 1e9 + 7;
struct Edge {
    int u, v, c;
};    
Edge ed[N];
struct Quer {
    int t, u, v;
};  
vector <int> g[N];
const int LG = 17;
int mx[N][LG], go[N][LG];
int tin[N], tout[N], timer = 0;
void dfs1(int u, int p) {
    tin[u] = timer++;
    go[u][0] = p; 
    for (int i = 1; i < LG; ++i) {
        go[u][i] = go[go[u][i - 1]][i - 1];
    }   
    for (int i : g[u]) {
        int v = ed[i].u ^ ed[i].v ^ u;        
        if (v != p) {
            dfs1(v, u);
        }   
    }   
    tout[u] = timer++;
}   
bool used[N];
void dfs2(int u, int p, int i) {
    if (i == -1 || used[i]) mx[u][0] = -INF;
    else mx[u][0] = ed[i].c;
    for (int i = 1; i < LG; ++i) {
        mx[u][i] = max(mx[u][i - 1], mx[go[u][i - 1]][i - 1]);
    }   
    for (int i : g[u]) {
        int v = ed[i].u ^ ed[i].v ^ u;        
        if (v != p) {
            dfs2(v, u, i);
        }   
    }   
}   
inline bool anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}   
inline int lca(int u, int v) {
    if (anc(u, v)) return u;
    for (int i = LG - 1; i >= 0; --i) {
        if (!anc(go[u][i], v)) u = go[u][i];
    }   
    return go[u][0];
}   
inline int getmax_(int u, int p) {
    if (u == p) return -INF;
    int ans = -INF;
    for (int i = LG - 1; i >= 0; --i) {
        if (!anc(go[u][i], p)) {
            ans = max(ans, mx[u][i]);
            u = go[u][i];
        }   
    }   
    return max(ans, mx[u][0]);
}   
inline int getmax(int u, int v) {
    int l = lca(u, v);
    return max(getmax_(u, l), getmax_(v, l));
}   

const int K = 2000;

struct Edge1 {
    int v, i;    
};  

vector <Edge1> g1[K + 1];
int cmp[N];
bool us[N];
void dfs3(int u, int c) {
    us[u] = 1; cmp[u] = c;
    for (int i : g[u]) {
        if (used[i]) continue;
        int v = ed[i].u ^ ed[i].v ^ u;        
        if (!us[v]) {
            dfs3(v, c);
        }   
    }   
}   

Quer d[N];
vector <int> l[K];

void dfs4(int u, int p, vector <int> &a, int d) {
    a.app(u);
    for (auto e : g1[cmp[u]]) {
        if (cmp[e.v] == p) continue;
        if (getmax(u, e.v) > d) continue;
        if (ed[e.i].c > d) continue;
        dfs4(e.v, cmp[u], a, d);
    }   
}

bool comp(int i, int j) {
    return d[i].v < d[j].v;
}   
bool comp1(Edge a, Edge b) {
    return a.c < b.c;
}   

int par[N], cnt[N];
int root(int u) {
    if (par[u] == u) return u;
    else return par[u] = root(par[u]);
}   
void merge(int u, int v) {
    u = root(u); v = root(v);
    if (u == v) return;
    if (cnt[v] < cnt[u]) swap(u, v);
    par[u] = v; cnt[v] += cnt[u];
}   

#ifdef HOME
double gettime() {
    return (double)clock() / CLOCKS_PER_SEC;
}
#endif

int ans[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> ed[i].u >> ed[i].v >> ed[i].c;
        ed[i].c *= -1;
        g[ed[i].u].app(i); g[ed[i].v].app(i);
    }   
    dfs1(1, 1);

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> d[i].t >> d[i].u >> d[i].v;
        d[i].v *= -1;
        if (d[i].t == 1) --d[i].u;
    }   

    for (int a = 0; ; ++a) {  
        memset(used, 0, sizeof used);
        if (a * K >= q) break;
        for (int b = 0; b < K; ++b) {
            int i = a * K + b;
            if (i >= q) break;
            if (d[i].t == 1) {
                used[d[i].u] = 1;
            }   
        }

        dfs2(1, 1, -1);

        memset(us, 0, sizeof us);         
        int c = 0;
        for (int i = 1; i <= n; ++i) {
            if (!us[i]) {
                dfs3(i, c++);
            }   
        }

        for (int i = 0; i <= K; ++i) {
            g1[i].clear();
        }   
        for (int i = 0; i < m; ++i) {
            if (used[i]) {
                g1[cmp[ed[i].u]].push_back({ed[i].v, i});
                g1[cmp[ed[i].v]].push_back({ed[i].u, i});
            }   
        }   

        for (int i = 0; i < K; ++i) {
            l[i].clear();
        }   
        for (int b = 0; b < K; ++b) {
            int i = a * K + b;
            if (i >= q) break;
            if (d[i].t == 1) {
                ed[d[i].u].c = d[i].v;
            }   
            else {
                dfs4(d[i].u, cmp[d[i].u], l[b], d[i].v);
            }   
        }        

        vector <int> quer;
        for (int b = 0; b < K; ++b) {
            int i = a * K + b;
            if (i >= q) break;
            if (d[i].t == 2) {  
                quer.app(i);
            }   
        }        
        sort(quer.begin(), quer.end(), comp);
        
        vector <Edge> se;
        for (int i = 0; i < m; ++i) {
            if (!used[i]) {
                se.push_back(ed[i]);
            }
        }   
        sort(se.begin(), se.end(), comp1);

        for (int i = 1; i <= n; ++i) {
            par[i] = i; cnt[i] = 1;
        }   
        int ptr = 0;
        for (int i : quer) {
            while (ptr < se.size() && se[ptr].c <= d[i].v) {
                merge(se[ptr].u, se[ptr].v);
                ++ptr;
            }
            for (int v : l[i - a * K]) {
                ans[i] += cnt[root(v)];
            }   
        }   
    }   
    for (int i = 0; i < q; ++i) {
        if (d[i].t == 2) {
            cout << ans[i] << '\n';
        }   
    }   

    #ifdef HOME
    cerr << gettime() << '\n';
    #endif
}  

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:222:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr < se.size() && se[ptr].c <= d[i].v) {
                    ~~~~^~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27