oj.uz

Submission #261690

# Submission time Handle Problem Language Result Execution time Memory
261690 2020-08-12T01:52:31 Z ttnhuy313 Collapse (JOI18_collapse) C++14
100 / 100
 4759 ms 54056 KB 
#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> qList[maxn];
int type[maxn] , from[maxn] , to[maxn];
int cliff_at[maxn] , date[maxn];
int in[maxn] , out[maxn];
int res[maxn];
 
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;
        }
        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 , sz;};
    void reset(){
        fill_n(lab,maxn,-1);cnt = cnt1 = 0;
        sz = 0;
    }
}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 : qList[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 to[a] < to[b];});
        sort(q.begin(),q.end(),[&](const int a , const int b){return cliff_at[a] < cliff_at[b];});
        int qi = 0 , qe = 0;
        Dsu.reset();
        for(int i = 0 ; i < n ; ++i){
            while(qe < norm.size() && to[norm[qe]] == i)Dsu.Merge(from[norm[qe]] , to[norm[qe]]),++qe;
            int tmp = Dsu.cnt;
            while(qi < q.size() && cliff_at[q[qi]] == i){
                int id = q[qi];
                int pre = Dsu.cur();
                for(auto & c : sp){
                    if(to[c] <= i && c <= date[id] && date[id] < out[c])Dsu.Merge(from[c],to[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 from[a] > from[b];});
        reverse(q.begin(),q.end());
        qi = 0 , qe = 0;
        Dsu.reset();
        for(int i = n - 1 ; i >= 0 ; --i){
            while(qe < norm.size() && from[norm[qe]] == i){
                Dsu.Merge(from[norm[qe]] , to[norm[qe]]),++qe;
            }
            while(qi < q.size() && cliff_at[q[qi]] == i - 1){
                int id = q[qi];
                int pre = Dsu.cur();
                for(auto & c : sp){
                    if(from[c] >= i && c <= date[id] && date[id] < out[c]){
                        Dsu.Merge(from[c],to[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];
        from[i] = X[i];to[i] = Y[i];
        if(from[i] > to[i])swap(from[i],to[i]);
    }
    for(int i = 0 ; i < q ; ++i){
        cliff_at[i] =  P[i]; date[i] = W[i];
        qList[date[i]].pb(i);
    }
    map<ii,int> mmap;
    for(int i = 0 ; i < m ; ++i){
        if(type[i] == 0){
            mmap[mp(from[i],to[i])] = i;
        }else{
            out[mmap[mp(from[i],to[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 *avrgv[]) {
	int N, C, qList;   
    freopen("A.INP","r",stdin);
    freopen("A.OUT","w",stdout);
	scanf("%d%d%d", &N, &C, &qList);
	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(qList), P(qList);
	for(int i = 0; i < qList; 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

collapse.cpp: In function 'void solve()':
collapse.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qe < norm.size() && to[norm[qe]] == i)Dsu.Merge(from[norm[qe]] , to[norm[qe]]),++qe;
                   ~~~^~~~~~~~~~~~~
collapse.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qi < q.size() && cliff_at[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() && from[norm[qe]] == i){
                   ~~~^~~~~~~~~~~~~
collapse.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(qi < q.size() && cliff_at[q[qi]] == i - 1){
                   ~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35064 KB Output is correct
2 Correct 23 ms 34688 KB Output is correct
3 Correct 26 ms 34688 KB Output is correct
4 Correct 24 ms 34688 KB Output is correct
5 Correct 33 ms 34944 KB Output is correct
6 Correct 46 ms 35320 KB Output is correct
7 Correct 26 ms 34680 KB Output is correct
8 Correct 23 ms 34752 KB Output is correct
9 Correct 36 ms 35192 KB Output is correct
10 Correct 51 ms 35192 KB Output is correct
11 Correct 63 ms 35320 KB Output is correct
12 Correct 57 ms 35360 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 38896 KB Output is correct
2 Correct 55 ms 39016 KB Output is correct
3 Correct 298 ms 46200 KB Output is correct
4 Correct 83 ms 39184 KB Output is correct
5 Correct 428 ms 46836 KB Output is correct
6 Correct 331 ms 39924 KB Output is correct
7 Correct 2549 ms 53364 KB Output is correct
8 Correct 505 ms 50232 KB Output is correct
9 Correct 58 ms 39272 KB Output is correct
10 Correct 76 ms 39272 KB Output is correct
11 Correct 413 ms 39808 KB Output is correct
12 Correct 616 ms 50712 KB Output is correct
13 Correct 1916 ms 51896 KB Output is correct
14 Correct 4427 ms 54056 KB Output is correct
15 Correct 3320 ms 53984 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 38888 KB Output is correct
2 Correct 65 ms 38820 KB Output is correct
3 Correct 73 ms 39084 KB Output is correct
4 Correct 92 ms 39164 KB Output is correct
5 Correct 387 ms 39472 KB Output is correct
6 Correct 363 ms 39788 KB Output is correct
7 Correct 1615 ms 49348 KB Output is correct
8 Correct 3372 ms 52664 KB Output is correct
9 Correct 79 ms 39260 KB Output is correct
10 Correct 557 ms 39560 KB Output is correct
11 Correct 3587 ms 53152 KB Output is correct
12 Correct 4759 ms 53292 KB Output is correct
13 Correct 3776 ms 52968 KB Output is correct
14 Correct 4582 ms 53176 KB Output is correct
15 Correct 3707 ms 52968 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35064 KB Output is correct
2 Correct 23 ms 34688 KB Output is correct
3 Correct 26 ms 34688 KB Output is correct
4 Correct 24 ms 34688 KB Output is correct
5 Correct 33 ms 34944 KB Output is correct
6 Correct 46 ms 35320 KB Output is correct
7 Correct 26 ms 34680 KB Output is correct
8 Correct 23 ms 34752 KB Output is correct
9 Correct 36 ms 35192 KB Output is correct
10 Correct 51 ms 35192 KB Output is correct
11 Correct 63 ms 35320 KB Output is correct
12 Correct 57 ms 35360 KB Output is correct
13 Correct 53 ms 38896 KB Output is correct
14 Correct 55 ms 39016 KB Output is correct
15 Correct 298 ms 46200 KB Output is correct
16 Correct 83 ms 39184 KB Output is correct
17 Correct 428 ms 46836 KB Output is correct
18 Correct 331 ms 39924 KB Output is correct
19 Correct 2549 ms 53364 KB Output is correct
20 Correct 505 ms 50232 KB Output is correct
21 Correct 58 ms 39272 KB Output is correct
22 Correct 76 ms 39272 KB Output is correct
23 Correct 413 ms 39808 KB Output is correct
24 Correct 616 ms 50712 KB Output is correct
25 Correct 1916 ms 51896 KB Output is correct
26 Correct 4427 ms 54056 KB Output is correct
27 Correct 3320 ms 53984 KB Output is correct
28 Correct 53 ms 38888 KB Output is correct
29 Correct 65 ms 38820 KB Output is correct
30 Correct 73 ms 39084 KB Output is correct
31 Correct 92 ms 39164 KB Output is correct
32 Correct 387 ms 39472 KB Output is correct
33 Correct 363 ms 39788 KB Output is correct
34 Correct 1615 ms 49348 KB Output is correct
35 Correct 3372 ms 52664 KB Output is correct
36 Correct 79 ms 39260 KB Output is correct
37 Correct 557 ms 39560 KB Output is correct
38 Correct 3587 ms 53152 KB Output is correct
39 Correct 4759 ms 53292 KB Output is correct
40 Correct 3776 ms 52968 KB Output is correct
41 Correct 4582 ms 53176 KB Output is correct
42 Correct 3707 ms 52968 KB Output is correct
43 Correct 469 ms 48588 KB Output is correct
44 Correct 2607 ms 52336 KB Output is correct
45 Correct 567 ms 49144 KB Output is correct
46 Correct 3429 ms 52520 KB Output is correct
47 Correct 71 ms 39144 KB Output is correct
48 Correct 83 ms 39400 KB Output is correct
49 Correct 448 ms 39692 KB Output is correct
50 Correct 625 ms 40952 KB Output is correct
51 Correct 760 ms 49272 KB Output is correct
52 Correct 1595 ms 49888 KB Output is correct
53 Correct 1411 ms 49476 KB Output is correct
54 Correct 2406 ms 51004 KB Output is correct
55 Correct 2013 ms 50632 KB Output is correct
56 Correct 2608 ms 51460 KB Output is correct
57 Correct 3230 ms 52416 KB Output is correct
58 Correct 3875 ms 52460 KB Output is correct
59 Correct 3568 ms 53276 KB Output is correct
60 Correct 4686 ms 52940 KB Output is correct