Submission #994379

#	Time	Username	Problem	Language	Result	Execution time	Memory
994379		yeediot	Bridges (APIO19_bridges)	C++17	14 / 100	836 ms	9816 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define tiii tuple<int, int, int>
#define toi_is_so_de ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void CHECK();
void setio(){
    freopen("/Users/iantsai/cpp/input.txt","r",stdin);
    freopen("/Users/iantsai/cpp/output.txt","w",stdout);
}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
const int mxn = 5e4+5, mxm = 1e5+5, siz = sqrt(mxm);
int n, m, q, v[mxm], id[mxm], ans[mxm], op[mxm], changed[mxm], a[mxm], b[mxm], c[mxm], x[mxm], y[mxm], ord[mxm];
bool vis[mxm];
struct DSU {
    int to[mxn], num[mxn];
    vector<int>adj[mxn];
    bool vs[mxn];
    void init(int n){
        for(int i = 1; i <= n; i++){
            to[i] = i;
            num[i] = 1;
        }
    }
    int find(int x){
        return x == to[x] ? x : to[x] = find(to[x]);
    }
    bool merge(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return false;
        if(num[x] < num[y])swap(x, y);
        to[y] = x;
        num[x] += num[y];
        return true;
    }
    int dfs(int v){
        int res = 0;
        vs[v] = 1;
        for(auto u : adj[v]){
            if(!vs[u]) res += dfs(u);
        }
        return res+num[v];
    }
    void dfs2(int v){
        vs[v] = 0;
        for(auto u : adj[v]){
            if(vs[u]) dfs2(u);
        }
    }
}d;
signed main(){
    setio();
    toi_is_so_de;
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    for(int i=1;i<=m;i++){
        ord[i] = i;
    }
    cin >> q;
    for(int i=1;i<=q;i++){
        cin >> op[i] >> x[i] >> y[i];
    }
    sort(ord+1, ord+1+m, [&](int i, int j){return c[i] > c[j];});
    for(int i=1;i<=q;i+=siz){
        d.init(n);
        vector<int> qres, temp;
        for(int j=min(q, i+siz-1);j>=i;j--){
            if(op[j] == 1){
                changed[x[j]] = j;
                temp.pb(x[j]);
            }
            else{
                qres.pb(j);
            }
        }
        sort(all(temp));
        temp.resize(unique(all(temp))-temp.begin());
        int pos = 0;
        sort(all(qres), [&](int i, int j){return y[i] > y[j];});
        for(auto t : qres){
            while(pos+1 <= m and c[ord[pos+1]] >= y[t]){
                pos++;
                if(changed[ord[pos]] == 0) d.merge(a[ord[pos]], b[ord[pos]]);
            }
            //int ro = sz(d.temp);
            for(int j=t;j>=i;j--){
                if(op[j] == 2 or vis[x[j]])continue;
                vis[x[j]] = 1;
                if(y[j] >= y[t]){
                    int l = d.find(a[x[j]]), r = d.find(b[x[j]]);
                    d.adj[l].pb(r);
                    d.adj[r].pb(l);
                }
            }
            for(auto x : temp){
                if(vis[x]) vis[x] = 0;
                else if(c[x] >= y[t]){
                    int l = d.find(a[x]), r = d.find(b[x]);
                    d.adj[l].pb(r);
                    d.adj[r].pb(l);
                }
            }
            ans[t] = d.dfs(d.find(x[t]));
            d.dfs2(d.find(x[t]));
            for(int j=t;j>=i;j--){
                if(op[j] == 2 or vis[x[j]])continue;
                vis[x[j]] = 1;
                if(y[j] >= y[t]){
                    int l = d.find(a[x[j]]), r = d.find(b[x[j]]);
                    d.adj[l].clear();
                    d.adj[r].clear();
                }
            }
            for(auto x : temp){
                if(vis[x]) vis[x] = 0;
                else if(c[x] >= y[t]){
                    int l = d.find(a[x]), r = d.find(b[x]);
                    d.adj[l].clear();
                    d.adj[r].clear();;
                }
            }
            //ans[t] = d.num[d.find(x[t])];
            //d.undo(ro);
        }
        int nword[m+1];
        vector<bool>ck(m+1);
        for(int j=i;j<=min(q,i+siz-1);j++){
            if(op[j] == 1){
                changed[x[j]] = 0;
                c[x[j]] = y[j];
                ck[x[j]] = 1;
            }
        }
        sort(all(temp), [&](int i, int j){return c[i] > c[j];});
        int cr = 0, cnt = 0;
        for(int i=1;i<=m;i++){
            if(ck[ord[i]])continue;
            while(cr < sz(temp) and c[ord[i]] < c[temp[cr]]){
                nword[++cnt] = temp[cr++];
            }
            nword[++cnt] = ord[i];
        }
        for(int i=1;i<=m;i++){
            ord[i] = nword[i];
        }
    }
    for(int i=1;i<=q;i++){
        if(ans[i]) cout<< ans[i] << '\n';
    }
}
#ifdef local
void CHECK(){
    cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
     function<bool(string,string)> compareFiles = [](string p1, string p2)->bool {
         std::ifstream file1(p1);
         std::ifstream file2(p2);
         if (!file1.is_open() || !file2.is_open())return false;
         std::string line1, line2;
         while (getline(file1, line1) && getline(file2, line2)) {
             if (line1 != line2)return false;
         }
         int cnta=0,cntb=0;
         while(getline(file1,line1))cnta++;
         while(getline(file2,line2))cntb++;
         return cntb-cnta<=1;
     };
     bool check = compareFiles("output.txt","expected.txt");
     if (check) cerr<<"ACCEPTED\n";
     else cerr<<"WRONG ANSWER!\n";
}
#else
#endif

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