Submission #993978

#	Time	Username	Problem	Language	Result	Execution time	Memory
993978		yeediot	Bridges (APIO19_bridges)	C++17	14 / 100	871 ms	142128 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define int long long
#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], changed[mxm];
tiii edges[mxm];
bool vis[mxm];
struct DSU {
    int to[mxn], num[mxn];
    vector<int> temp;
    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){
        debug(x, y);
        x = find(x), y = find(y);
        if(x == y)return false;
        if(num[x] < num[y])swap(x, y);
        temp.pb(y);
        to[y] = x;
        num[x] += num[y];
        return true;
    }
    void undo(int ed){
        debug(sz(temp), ed);
        while(sz(temp) > ed){
            auto y = temp.back();
            num[to[y]] -= num[y];
            to[y] = y;
            temp.pop_back();
        }
    }
}d;
signed main(){
    setio();
    toi_is_so_de;
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    int ord[m+1];
    for(int i=1;i<=m;i++){
        ord[i] = i;
    }
    sort(ord+1, ord+1+m, [&](int a, int b){return get<2>(edges[a]) > get<2>(edges[b]);});
    cin >> q;
    for(int i=1;i<=q;i+=siz){
        d.init(n);
        vector<tiii>qres;
        vector<int>temp;
        for(int j=i;j<=min(q, i+siz-1);j++){
            int ty, x, y;
            cin >> ty >> x >> y;
            if(ty == 1){
                changed[x] = j;
                id[j] = x, v[j] = y;
                temp.pb(x);
            }
            else{
                qres.pb({y, x, j});
            }
        }
        sort(all(temp));
        temp.resize(unique(all(temp))-temp.begin());
        int pos = 0;
        sort(all(qres), greater<tiii>());
        for(auto [w, st, t] : qres){
            while(pos+1 <= m and get<2>(edges[ord[pos+1]])>=w){
                pos++;
                if(changed[ord[pos]] == 0) d.merge(get<0>(edges[ord[pos]]), get<1>(edges[ord[pos]]));
            }
            int ro = sz(d.temp);
            for(int j=t;j>=i;j--){
                if(!id[j] or vis[id[j]])continue;
                vis[id[j]] = 1;
                if(v[j]>=w){
                    d.merge(get<0>(edges[id[j]]),get<1>(edges[id[j]]));
                }
            }
            for(auto x:temp){
                if(vis[x]) vis[x] = 0;
                else if(get<2>(edges[x])>=w){
                    d.merge(get<0>(edges[x]),get<1>(edges[x]));
                    debug("1");
                }
            }
            ans[t] = d.num[d.find(st)];
            d.undo(ro);
        }
    }
    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