Submission #202908

#	Time	Username	Problem	Language	Result	Execution time	Memory
202908		Mercenary	Collapse (JOI18_collapse)	C++14	35 / 100	4777 ms	26760 KiB

collapse

#ifndef LOCAL
#include "collapse.h"
#endif // LOCAL
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;
const int maxn = 1e5 + 5;
typedef pair<int,int> ii;

int n , m , q;
vector<int> Q[maxn];
int type[maxn] , x[maxn] , y[maxn];
int p[maxn] , w[maxn];
int in[maxn] , out[maxn];
int res[maxn];

struct Dsurollback{
    vector<pair<int*,int>> data;
    int lab[maxn];
    int FindLab(int u){
        return lab[u] < 0 ? u : FindLab(lab[u]);
    }
    void Change(int & u , int v){
        data.pb(mp(&u,u));
        u = v;
    }
    void rollback(int sz){
        while(data.size() > sz){
            (*data.back().first) = data.back().second;
            data.pop_back();
        }
        cnt -= cnt1;
        cnt1 = 0;
    }
    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);
        cnt++;cnt1++;
    }
    int cur(){return cnt1 = 0 , data.size();};
    void reset(){
        fill_n(lab,maxn,-1);cnt = cnt1 = 0;
        data.clear();
    }
}Dsu;

void solve(){
    const int MAGIC = 400;
    for(int l = 0 ; l < m ; l += MAGIC){
        vector<int> sp  , norm,q;
        int r = min(m,l+MAGIC) - 1;
        for(int i = 0 ; i <= r ; ++i){
            if(i >= l)for(auto & id : Q[i])q.pb(id);
            if(out[i] < l || type[i] == 1)continue;
            if(i < l && out[i] > r)norm.pb(i);
            else sp.pb(i);
        }
        sort(norm.begin(),norm.end(),[&](const int a , const int b){return y[a] < y[b];});
        sort(q.begin(),q.end(),[&](const int a , const int b){return p[a] < p[b];});
        int qi = 0 , qe = 0;
        Dsu.reset();
        for(int i = 0 ; i < n ; ++i){
            while(qe < norm.size() && y[norm[qe]] == i)Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe;
            int tmp = Dsu.cnt;
            while(qi < q.size() && p[q[qi]] == i){
                int id = q[qi];
                int pre = Dsu.cur();
                for(auto & c : sp){
                    if(y[c] <= i && c <= w[id] && w[id] < out[c])Dsu.Merge(x[c],y[c]);
                }
                res[id] -= Dsu.cnt;
                Dsu.rollback(pre);
                ++qi;
            }
        }
//        cerr << norm.size() << " " << Dsu.cnt << endl;
        sort(norm.begin(),norm.end(),[&](const int a , const int b){return x[a] > x[b];});
        reverse(q.begin(),q.end());
        qi = 0 , qe = 0;
        Dsu.reset();
        for(int i = n - 1 ; i >= 0 ; --i){
            while(qe < norm.size() && x[norm[qe]] == i){
                Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe;
            }
            while(qi < q.size() && p[q[qi]] == i - 1){
                int id = q[qi];
                int pre = Dsu.cur();
                for(auto & c : sp){
                    if(x[c] >= i && c <= w[id] && w[id] < out[c]){
                        Dsu.Merge(x[c],y[c]);
                    }
                }
                res[id] -= Dsu.cnt;
                Dsu.rollback(pre);
                ++qi;
            }
        }
    }
}

vector<int> simulateCollapse(int N,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P)
{
    n = N;m = T.size();q = W.size();
    for(int i = 0 ; i < m ; ++i){
        type[i] = T[i];
        x[i] = X[i];y[i] = Y[i];
        if(x[i] > y[i])swap(x[i],y[i]);
    }
    for(int i = 0 ; i < q ; ++i){
        p[i] =  P[i];w[i] = W[i];
        Q[w[i]].pb(i);
    }
    map<ii,int> mmap;
    for(int i = 0 ; i < m ; ++i){
        if(type[i] == 0){
            mmap[mp(x[i],y[i])] = i;
        }else{
            out[mmap[mp(x[i],y[i])]] = i;
        }
    }
    for(int i = 0 ; i < m ; ++i)if(type[i] == 0 && out[i] == 0)out[i] = m;
    solve();
    vector<int> res;
    for(int i = 0 ; i < q ; ++i)res.pb(::res[i] + n);
    return res;
}


#ifdef LOCAL
int main(int argc, char *argv[]) {
	int N, C, Q;
    freopen("A.INP","r",stdin);
    freopen("A.OUT","w",stdout);
	scanf("%d%d%d", &N, &C, &Q);
	std::vector<int> T(C), X(C), Y(C);
	for(int i = 0; i < C; i++) {
		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
	}
	std::vector<int> W(Q), P(Q);
	for(int i = 0; i < Q; i++) {
		scanf("%d%d", &W[i], &P[i]);
	}
	auto res = simulateCollapse(N, T, X, Y, W, P);
	for(auto i : res) {
		printf("%d\n", i);
	}
}
#endif

Compilation message (stderr)

collapse.cpp: In member function 'void Dsurollback::rollback(int)':
collapse.cpp:30:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(data.size() > sz){
               ~~~~~~~~~~~~^~~~
collapse.cpp: In function 'void solve()':
collapse.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qe < norm.size() && y[norm[qe]] == i)Dsu.Merge(x[norm[qe]] , y[norm[qe]]),++qe;
                   ~~~^~~~~~~~~~~~~
collapse.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qi < q.size() && p[q[qi]] == i){
                   ~~~^~~~~~~~~~
collapse.cpp:71:17: warning: unused variable 'tmp' [-Wunused-variable]
             int tmp = Dsu.cnt;
                 ^~~
collapse.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qe < norm.size() && x[norm[qe]] == i){
                   ~~~^~~~~~~~~~~~~
collapse.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qi < q.size() && p[q[qi]] == i - 1){
                   ~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35