oj.uz

Submission #411474

# Submission time Handle Problem Language Result Execution time Memory
411474 2021-05-25T11:33:12 Z mhy908 Collapse (JOI18_collapse) C++14
100 / 100
 14576 ms 148120 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;

const int BUC=300;

struct UNION_FIND{
    int par[100010], sz[100010], cnt;
    vector<int> vc;
    void init(int num){for(int i=1; i<=num; i++)par[i]=i, sz[i]=1; cnt=0;}
    int findpar(int num){return num==par[num]?num:findpar(par[num]);}
    void mergepar(int a, int b){
        a=findpar(a);
        b=findpar(b);
        if(a==b)return;
        if(sz[a]<sz[b])swap(a, b);
        vc.eb(b);
        par[b]=a;
        sz[a]+=sz[b];
        cnt++;
    }
    void rollback(){
        int tmp=vc.back();
        vc.pop_back();
        sz[par[tmp]]-=sz[tmp];
        par[tmp]=tmp;
        cnt--;
    }
}uf;

int n, m, q, query[100010], ans[100010];
pair<int, pii> edge[100010];
vector<int> qlst[100010];

bool cmpl(pii a, pii b){return a.S<b.S;}
bool cmpr(pii a, pii b){return a.F>b.F;}

void solve(int s, int e){

    set<pii> edgs;
    for(int i=1; i<s; i++){
        if(edge[i].F==0)edgs.insert(edge[i].S);
        else edgs.erase(edge[i].S);
    }
    vector<pii> org;
    for(int i=s; i<=e; i++){
        if(edge[i].F&&edgs.find(edge[i].S)!=edgs.end()){
            edgs.erase(edge[i].S);
            org.eb(edge[i].S);
        }
    }

    vector<pair<int, pii> > nq;
    for(int i=s; i<=e; i++){
        for(auto j:qlst[i])nq.eb(query[j], mp(i, j));
    }

    vector<pii> nedge;
    for(auto i:edgs)nedge.eb(i);

    sort(all(nedge), cmpl);
    sort(all(nq));
    uf.init(n);

    int pv=0;
    for(auto i:nq){
        for(; pv<nedge.size(); pv++){
            if(nedge[pv].S>i.F)break;
            uf.mergepar(nedge[pv].F, nedge[pv].S);
        }
        set<pii> nadd;
        for(auto j:org)nadd.insert(j);
        for(int j=s; j<=i.S.F; j++){
            if(edge[j].F==0)nadd.insert(edge[j].S);
            else nadd.erase(edge[j].S);
        }

        int nsz=uf.vc.size();

        for(auto j:nadd){
            if(j.S<=i.F)uf.mergepar(j.F, j.S);
        }

        ans[i.S.S]+=i.F-uf.cnt;

        while(uf.vc.size()>nsz)uf.rollback();

    }

    sort(all(nedge), cmpr);
    reverse(all(nq));
    uf.init(n);
    pv=0;
    
    for(auto i:nq){
        for(; pv<nedge.size(); pv++){
            if(nedge[pv].F<=i.F)break;
            uf.mergepar(nedge[pv].F, nedge[pv].S);
        }
        set<pii> nadd;
        for(auto j:org)nadd.insert(j);
        for(int j=s; j<=i.S.F; j++){
            if(edge[j].F==0)nadd.insert(edge[j].S);
            else nadd.erase(edge[j].S);
        }

        int nsz=uf.vc.size();

        for(auto j:nadd){
            if(j.F>i.F)uf.mergepar(j.F, j.S);
        }

        ans[i.S.S]+=n-i.F-uf.cnt;

        while(uf.vc.size()>nsz)uf.rollback();

    }

}

/*
int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=m; i++){
        scanf("%d %d %d", &edge[i].F, &edge[i].S.F, &edge[i].S.S);
        if(edge[i].S.F>edge[i].S.S)swap(edge[i].S.F, edge[i].S.S);
        edge[i].S.F++, edge[i].S.S++;
    }
    for(int i=1; i<=q; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        qlst[a+1].eb(i);
        query[i]=b+1;
    }

    for(int i=1; i<=m; i+=BUC)solve(i, min(m, i+BUC-1));
    for(int i=1; i<=q; i++)printf("%d\n", ans[i]);
}
*/

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=1; i<=m; i++){
        edge[i].F=T[i-1];
        edge[i].S.F=X[i-1];
        edge[i].S.S=Y[i-1];
        if(edge[i].S.F>edge[i].S.S)swap(edge[i].S.F, edge[i].S.S);
        edge[i].S.F++, edge[i].S.S++;
    }
    
    for(int i=1; i<=q; i++){
        int a=W[i-1], b=P[i-1];
        qlst[a+1].eb(i);
        query[i]=b+1;
    }
    
    vector<int> ret;
    
    for(int i=1; i<=m; i+=BUC)solve(i, min(m, i+BUC-1));
    for(int i=1; i<=q; i++)ret.eb(ans[i]);
    
    return ret;
}

Compilation message

collapse.cpp: In function 'void solve(int, int)':
collapse.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(; pv<nedge.size(); pv++){
      |               ~~^~~~~~~~~~~~~
collapse.cpp:94:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         while(uf.vc.size()>nsz)uf.rollback();
      |               ~~~~~~~~~~~~^~~~
collapse.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(; pv<nedge.size(); pv++){
      |               ~~^~~~~~~~~~~~~
collapse.cpp:123:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |         while(uf.vc.size()>nsz)uf.rollback();
      |               ~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3112 KB Output is correct
2 Correct 6 ms 2892 KB Output is correct
3 Correct 14 ms 2972 KB Output is correct
4 Correct 20 ms 2972 KB Output is correct
5 Correct 142 ms 3052 KB Output is correct
6 Correct 200 ms 3356 KB Output is correct
7 Correct 5 ms 3016 KB Output is correct
8 Correct 11 ms 3020 KB Output is correct
9 Correct 117 ms 3100 KB Output is correct
10 Correct 254 ms 3228 KB Output is correct
11 Correct 211 ms 3920 KB Output is correct
12 Correct 211 ms 3936 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6888 KB Output is correct
2 Correct 70 ms 6916 KB Output is correct
3 Correct 4434 ms 12184 KB Output is correct
4 Correct 327 ms 7036 KB Output is correct
5 Correct 6148 ms 12288 KB Output is correct
6 Correct 2872 ms 6888 KB Output is correct
7 Correct 11884 ms 19460 KB Output is correct
8 Correct 5952 ms 12336 KB Output is correct
9 Correct 47 ms 7732 KB Output is correct
10 Correct 113 ms 7528 KB Output is correct
11 Correct 2687 ms 7664 KB Output is correct
12 Correct 5794 ms 13120 KB Output is correct
13 Correct 10556 ms 31036 KB Output is correct
14 Correct 12509 ms 84652 KB Output is correct
15 Correct 11530 ms 50324 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6964 KB Output is correct
2 Correct 81 ms 6772 KB Output is correct
3 Correct 174 ms 6968 KB Output is correct
4 Correct 335 ms 7028 KB Output is correct
5 Correct 2959 ms 6756 KB Output is correct
6 Correct 3566 ms 6752 KB Output is correct
7 Correct 8135 ms 16516 KB Output is correct
8 Correct 13140 ms 48448 KB Output is correct
9 Correct 53 ms 7740 KB Output is correct
10 Correct 3469 ms 7208 KB Output is correct
11 Correct 13253 ms 147940 KB Output is correct
12 Correct 14570 ms 147592 KB Output is correct
13 Correct 13975 ms 148068 KB Output is correct
14 Correct 14576 ms 147544 KB Output is correct
15 Correct 13081 ms 148120 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3112 KB Output is correct
2 Correct 6 ms 2892 KB Output is correct
3 Correct 14 ms 2972 KB Output is correct
4 Correct 20 ms 2972 KB Output is correct
5 Correct 142 ms 3052 KB Output is correct
6 Correct 200 ms 3356 KB Output is correct
7 Correct 5 ms 3016 KB Output is correct
8 Correct 11 ms 3020 KB Output is correct
9 Correct 117 ms 3100 KB Output is correct
10 Correct 254 ms 3228 KB Output is correct
11 Correct 211 ms 3920 KB Output is correct
12 Correct 211 ms 3936 KB Output is correct
13 Correct 44 ms 6888 KB Output is correct
14 Correct 70 ms 6916 KB Output is correct
15 Correct 4434 ms 12184 KB Output is correct
16 Correct 327 ms 7036 KB Output is correct
17 Correct 6148 ms 12288 KB Output is correct
18 Correct 2872 ms 6888 KB Output is correct
19 Correct 11884 ms 19460 KB Output is correct
20 Correct 5952 ms 12336 KB Output is correct
21 Correct 47 ms 7732 KB Output is correct
22 Correct 113 ms 7528 KB Output is correct
23 Correct 2687 ms 7664 KB Output is correct
24 Correct 5794 ms 13120 KB Output is correct
25 Correct 10556 ms 31036 KB Output is correct
26 Correct 12509 ms 84652 KB Output is correct
27 Correct 11530 ms 50324 KB Output is correct
28 Correct 44 ms 6964 KB Output is correct
29 Correct 81 ms 6772 KB Output is correct
30 Correct 174 ms 6968 KB Output is correct
31 Correct 335 ms 7028 KB Output is correct
32 Correct 2959 ms 6756 KB Output is correct
33 Correct 3566 ms 6752 KB Output is correct
34 Correct 8135 ms 16516 KB Output is correct
35 Correct 13140 ms 48448 KB Output is correct
36 Correct 53 ms 7740 KB Output is correct
37 Correct 3469 ms 7208 KB Output is correct
38 Correct 13253 ms 147940 KB Output is correct
39 Correct 14570 ms 147592 KB Output is correct
40 Correct 13975 ms 148068 KB Output is correct
41 Correct 14576 ms 147544 KB Output is correct
42 Correct 13081 ms 148120 KB Output is correct
43 Correct 5146 ms 11208 KB Output is correct
44 Correct 12183 ms 19968 KB Output is correct
45 Correct 5936 ms 11424 KB Output is correct
46 Correct 13111 ms 48268 KB Output is correct
47 Correct 54 ms 7652 KB Output is correct
48 Correct 105 ms 7572 KB Output is correct
49 Correct 3547 ms 7432 KB Output is correct
50 Correct 4508 ms 9508 KB Output is correct
51 Correct 6721 ms 12092 KB Output is correct
52 Correct 9933 ms 45124 KB Output is correct
53 Correct 10192 ms 45164 KB Output is correct
54 Correct 11138 ms 79024 KB Output is correct
55 Correct 10939 ms 79056 KB Output is correct
56 Correct 11703 ms 146400 KB Output is correct
57 Correct 12552 ms 147424 KB Output is correct
58 Correct 13123 ms 146608 KB Output is correct
59 Correct 12968 ms 148056 KB Output is correct
60 Correct 14249 ms 147604 KB Output is correct