제출 #676192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676192		fatemetmhr	다리 (APIO19_bridges)	C++17	100 / 100	2898 ms	14560 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   =  500;
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];
bool dis[maxn5], seen[maxn5], mark[maxn5];
vector <int> adj[maxn5], wi;
int plc[maxn5], toadd[maxn5], cnt[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(cnt, 0, sizeof cnt);
        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--;
        int edind = 0;
        for(int i = bl - 1; i >= 0; i--) if(ty[i] == 1){
            if(!mark[x[i]]){
                mark[x[i]] = true;
                cnt[indqu[i]]++;
                last[x[i]] = y[i];
                toadd[edind++] = i + 1;
            }
            else if(last[x[i]] == -1)
                last[x[i]] = y[i];
        }
        for(int i = 0; i < m; i++){
            if(!mark[i]){
                cnt[inded[i]]++;
                toadd[edind++] = -i;
                last[i] = c[i];
            }
            else if(last[i] == -1)
                last[i] = c[i];
        }
        for(int i = 1; i < wi.size(); i++)
            cnt[i] += cnt[i - 1];
        for(int i = 0; i < edind; i++){
            if(toadd[i] <= 0) 
                plc[--cnt[inded[-toadd[i]]]] = toadd[i];
            else
                plc[--cnt[indqu[toadd[i] - 1]]] = toadd[i];
        }
        while(verind >= 0 && edind--){
            int edd = -plc[edind];
            if(edd < 0)
                edd = x[edd * -1 - 1];
            while(verind >= 0 && y[ver[verind]] > last[edd]){
                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;
            }
            int u = get_par(a[edd]);
            int v = get_par(b[edd]);
            if(u == v)
                continue;
            if(par[u] > par[v])
                swap(u, v);
            par[u] += par[v];
            par[v] = u;
        }
        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!

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

bridges.cpp: In function 'int main()':
bridges.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int i = 1; i < wi.size(); i++)
      |                        ~~^~~~~~~~~~~

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