Submission #203085

#	Time	Username	Problem	Language	Result	Execution time	Memory
203085		Mercenary	Bridges (APIO19_bridges)	C++14	100 / 100	2543 ms	42016 KiB

bridges

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;

struct Dsurollback{
    pair<int*,int> data[(int)2e6];
    int lab[maxn] , sz;
    int FindLab(int u){
        return lab[u] < 0 ? u : FindLab(lab[u]);
    }
    void Change(int & u , int v){
        data[sz++] = mp(&u,u);
        u = v;
    }
    void rollback(int sz1){
        while(sz > sz1){
            (*data[sz-1].first) = data[sz-1].second;
            --sz;
        }
    }
    int cnt = 0;
    int cnt1 = 0;
    void Merge(int u , int v){
        u = FindLab(u);v = FindLab(v);
        if(u == v)return;
        if(lab[u] > lab[v])swap(u,v);
        Change(lab[u],lab[u]+lab[v]);
        Change(lab[v],u);
    }
    int cur(){return sz;};
    void reset(int n){
        fill_n(lab,n+2,-1);
        sz = 0;
    }
}Dsu;

int n , m , q;
int u[maxn] , v[maxn] , d[maxn];
int out[maxn] , fakeid[maxn];
int type[maxn];
int res[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m;
    for(int i = 1 ;  i <= m ; ++i){
        cin >> u[i] >> v[i] >> d[i];
        fakeid[i] = i;
    }
    cin >> q;
    for(int i = m + 1 ; i <= q + m ; ++i){
        cin >> type[i];
        if(type[i] == 1){
            int x;cin >> x;
            u[i] = u[x];v[i] = v[x];cin >> d[i];
            out[fakeid[x]] = i;
            fakeid[x] = i;
        }else{
            cin >> u[i] >> d[i];
        }
    }
    for(int i = 1 ; i <= m + q ; ++i)if(out[i] == 0)out[i] = q + m + 1;
    const int MAGIC = 300;
    vector<int> prepare;
    for(int i = 1 ; i <= m + q ; ++i)if(type[i] != 2)prepare.pb(i);
    sort(prepare.begin(),prepare.end() , [&](const int x , const int y){return d[x] > d[y];});
    for(int l = m + 1 ; l <= m + q ; l += MAGIC){
        int r = min(m + q ,l+MAGIC-1);
        vector<int> qval;
        Dsu.reset(n);
        vector<int> sp , norm;
        for(int i = l ; i <= r ; ++i){
            if(type[i] == 2 && i >= l)qval.pb(i);
        }
        for(auto & i : prepare){
            if(i > r || out[i] < l)continue;
            if(i < l && out[i] > r)norm.pb(i);
            else sp.pb(i);
        }
        sort(qval.begin(),qval.end(),[&](const int x , const int y){return d[x] > d[y];});
        int it = 0;
        for(auto & id : qval){
            while(it < norm.size() && d[id] <= d[norm[it]]){
                Dsu.Merge(u[norm[it]],v[norm[it]]);
                ++it;
            }
            int tmp = Dsu.cur();
            for(auto & c : sp){
                if(d[id] > d[c])break;
                if(d[id] <= d[c] && c < id && out[c] > id){
                    Dsu.Merge(u[c],v[c]);
                }
            }
            res[id] = -Dsu.lab[Dsu.FindLab(u[id])];
            Dsu.rollback(tmp);
        }
    }
    for(int i = m + 1 ; i <= m + q ; ++i)if(type[i] == 2)cout << res[i] << '\n';
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:104:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(it < norm.size() && d[id] <= d[norm[it]]){
                   ~~~^~~~~~~~~~~~~
bridges.cpp:63:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:64:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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