Submission #676186

#	Time	Username	Problem	Language	Result	Execution time	Memory
676186		fatemetmhr	Bridges (APIO19_bridges)	C++17	60 / 100	3058 ms	31588 KiB

bridges

// ~ Be Name Khoda ~

#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int ssq   =  600;
const ll  inf   =  1e18;

int a[maxn5], b[maxn5], c[maxn5], ty[maxn5], x[maxn5];
int y[maxn5], inded[maxn5], indqu[maxn5], par[maxn5];
int ver[maxn5], q[maxn5], out[maxn5], last[maxn5];
int sz[maxn5];
bool dis[maxn5], seen[maxn5], mark[maxn5];
vector <int> adj[maxn5], wi, st[maxn5 << 1];

inline bool cmp(int i, int j){return y[i] < y[j];}

int get_par(int a){return par[a] < 0 ? a : par[a] = get_par(par[a]);}

inline int bfs(int sr){
    int l = 0, r = 1, ret = 0;
    dis[sr] = true;
    q[0] = sr;
    while(l < r){
        int v = q[l++];
        ret -= par[v];
        for(auto u : adj[v]){
            if(!dis[u]){
                q[r++] = u;
                dis[u] = true;
            }
        }
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        wi.pb(c[i]);
    }
    int q; cin >> q;
    for(int i = 0; i < q; i++){
        cin >> ty[i] >> x[i] >> y[i];
        x[i]--;
        if(ty[i] == 1)
            wi.pb(y[i]);
    }
    sort(all(wi));
    wi.resize(unique(all(wi)) - wi.begin());
    for(int i = 0; i < m; i++)
        inded[i] = lower_bound(all(wi), c[i]) - wi.begin();
    for(int i = 0; i < q; i++) if(ty[i] == 1)
        indqu[i] = lower_bound(all(wi), y[i]) - wi.begin();
    for(int bl = 0; bl < q; bl += ssq){
        memset(mark, false, sizeof mark);
        memset(last, -1, sizeof last);
        memset(par, -1, sizeof par);
        memset(sz, -1, sizeof sz);
        int verind = 0;
        for(int i = bl; i < min(q, bl + ssq); i++){
            if(ty[i] == 1) 
                mark[x[i]] = true;
            else
                ver[verind++] = i;
        }
        sort(ver, ver + verind, cmp);
        verind--;
        for(int i = bl - 1; i >= 0; i--) if(ty[i] == 1){
            if(!mark[x[i]]){
                mark[x[i]] = true;
                st[indqu[i]].pb(x[i]);
                last[x[i]] = y[i];
            }
            else if(last[x[i]] == -1)
                last[x[i]] = y[i];
        }
        for(int i = 0; i < m; i++){
            if(!mark[i])
                st[inded[i]].pb(i);
            else if(last[i] == -1)
                last[i] = c[i];
        }
        for(int i = wi.size() - 1; i >= 0; i--) if(st[i].size()){
            while(verind >= 0 && y[ver[verind]] > wi[i]){
                int id = ver[verind--];
                for(int j = id; j >= bl; j--) if(ty[j] == 1 && !seen[x[j]]){
                    seen[x[j]] = true;
                    if(y[j] < y[id])
                        continue;
                    adj[get_par(a[x[j]])].pb(get_par(b[x[j]]));
                    adj[get_par(b[x[j]])].pb(get_par(a[x[j]]));
                }
                for(int j = id; j < min(bl + ssq, q); j++) if(!seen[x[j]] && last[x[j]] >= y[id]){
                    adj[get_par(a[x[j]])].pb(get_par(b[x[j]]));
                    adj[get_par(b[x[j]])].pb(get_par(a[x[j]]));
                }
                out[id] = bfs(get_par(x[id]));
                for(int j = id; j < min(bl + ssq, q); j++) if(!seen[x[j]] && last[x[j]] >= y[id]){
                    adj[get_par(a[x[j]])].clear();
                    adj[get_par(b[x[j]])].clear();
                    dis[get_par(a[x[j]])] = dis[get_par(b[x[j]])] = false;
                }
                for(int j = id; j >= bl; j--) if(ty[j] == 1){
                    seen[x[j]] = false; 
                    dis[get_par(a[x[j]])] = dis[get_par(b[x[j]])] = false;
                    adj[get_par(a[x[j]])].clear();
                    adj[get_par(b[x[j]])].clear();
                }
                dis[get_par(x[id])] = false;
            }
            if(verind == -1){
                st[i].clear();
                continue;
            }
            for(auto id : st[i]){
                int u = get_par(a[id]), v = get_par(b[id]);
                if(u == v)
                    continue;
                if(sz[u] > sz[v])
                    swap(u, v);
                par[u] += par[v];
                sz[u] += (sz[u] == sz[v]);
                par[v] = u;
            }
            st[i].clear();
        }
        while(verind >= 0){
            int id = ver[verind--];
            for(int j = id; j >= bl; j--) if(ty[j] == 1 && !seen[x[j]]){
                seen[x[j]] = true;
                if(y[j] < y[id])
                    continue;
                adj[get_par(a[x[j]])].pb(get_par(b[x[j]]));
                adj[get_par(b[x[j]])].pb(get_par(a[x[j]]));
            }
            for(int j = id; j < min(bl + ssq, q); j++) if(!seen[x[j]] && last[x[j]] >= y[id]){
                adj[get_par(a[x[j]])].pb(get_par(b[x[j]]));
                adj[get_par(b[x[j]])].pb(get_par(a[x[j]]));
            }
            out[id] = bfs(get_par(x[id]));
            for(int j = id; j < min(bl + ssq, q); j++) if(!seen[x[j]] && last[x[j]] >= y[id]){
                adj[get_par(a[x[j]])].clear();
                adj[get_par(b[x[j]])].clear();
                dis[get_par(a[x[j]])] = dis[get_par(b[x[j]])] = false;
            }
            for(int j = id; j >= bl; j--) if(ty[j] == 1){
                seen[x[j]] = false; 
                dis[get_par(a[x[j]])] = dis[get_par(b[x[j]])] = false;
                adj[get_par(a[x[j]])].clear();
                adj[get_par(b[x[j]])].clear();
            }
            dis[get_par(x[id])] = false;
        }
    }
    for(int i = 0; i < q; i++) if(ty[i] == 2)
        cout << out[i] << '\n';
}

// Heib!

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