oj.uz

Submission #144514

# Submission time Handle Problem Language Result Execution time Memory
144514 2019-08-17T01:47:49 Z Lyestria Split the Attractions (IOI19_split) C++14
100 / 100
 169 ms 18660 KB 
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int mn=2e5+10;
int p[mn],si[mn];
inline int f(int x){return x==p[x]?x:(p[x]=f(p[x]));}
inline int siz(int x){return si[f(x)];}
void mrg(int a,int b){a=f(a),b=f(b);if(a==b);else if(si[a]>si[b])si[a]+=si[b],p[b]=a;else si[b]+=si[a],p[a]=b;}
void init(){iota(p,p+mn,0);fill(si,si+mn,1);}
bool u[mn];
vector<int>g[mn],ans;
int s[mn];
int ctr,n;
void dfs(int x,int p){
    s[x]=1;
    for(int y:g[x]){
        if(y==p)continue;
        dfs(y,x);
        s[x]+=s[y];
    }
}
int fc(int x,int p){
    for(int y:g[x]){
        if(y==p)continue;
        if(s[y]*2>=n)return fc(y,x);
    }
    return x;
}
void dfs2(int x,int p){
    for(int y:g[x]){
        if(y==p)continue;
        dfs2(y,x);
        mrg(x,y);
    }
}
int lef,tar;
bool vis[mn];
int conv[4];
void dfs3(int x){
    if(!lef)return;
    vis[x]=1;
    lef--;
    ans[x]=conv[tar];
    for(int y:g[x]){
        if(!vis[y]){
            dfs3(y);
            if(!lef)return;
        }
    }
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
    int sm=min(a,min(b,c)),bi=max(a,max(b,c));
    if(a==sm)conv[1]=1;
    else if(a==bi)conv[3]=1;
    else conv[2]=1;
    if(b==sm&&!conv[1])conv[1]=2;
    else if(b==bi&&!conv[3])conv[3]=2;
    else conv[2]=2;
    if(c==sm&&!conv[1])conv[1]=3;
    else if(c==bi&&!conv[3])conv[3]=3;
    else conv[2]=3;
    b=a+b+c-sm-bi;
    a=sm;
    c=bi;
    n=N;
    ans.resize(n,conv[3]);
	int m=p.size(),i;
	init();
	for(i=0;i<m;i++){
        if(f(p[i])!=f(q[i])){
            mrg(p[i],q[i]);
            g[p[i]].push_back(q[i]);
            g[q[i]].push_back(p[i]);
        }
	}
	dfs(0,-1);
	ctr=fc(0,-1);
	init();
    for(int y:g[ctr]){
        dfs2(y,ctr);
        if(siz(y)>=a){
            vis[ctr]=1;
            lef=a;
            tar=1;
            dfs3(y);
            lef=b;
            tar=2;
            vis[ctr]=0;
            dfs3(ctr);
            return ans;
        }
    }
    for(i=0;i<m;i++){
        if(p[i]==ctr||q[i]==ctr)continue;
        if(f(p[i])==f(q[i]))continue;
        mrg(p[i],q[i]);
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
        if(siz(p[i])>=a){
            vis[ctr]=1;
            lef=a;
            tar=1;
            dfs3(p[i]);
            lef=b;
            tar=2;
            vis[ctr]=0;
            dfs3(ctr);
            return ans;
        }
    }
    fill(ans.begin(),ans.end(),0);
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6648 KB ok, correct split
2 Correct 8 ms 6520 KB ok, correct split
3 Correct 7 ms 6524 KB ok, correct split
4 Correct 8 ms 6648 KB ok, correct split
5 Correct 8 ms 6648 KB ok, correct split
6 Correct 8 ms 6648 KB ok, correct split
7 Correct 122 ms 18552 KB ok, correct split
8 Correct 107 ms 16632 KB ok, correct split
9 Correct 120 ms 16120 KB ok, correct split
10 Correct 122 ms 18660 KB ok, correct split
11 Correct 111 ms 17528 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6520 KB ok, correct split
2 Correct 8 ms 6648 KB ok, correct split
3 Correct 8 ms 6648 KB ok, correct split
4 Correct 108 ms 13384 KB ok, correct split
5 Correct 92 ms 12664 KB ok, correct split
6 Correct 123 ms 18424 KB ok, correct split
7 Correct 119 ms 16604 KB ok, correct split
8 Correct 119 ms 14020 KB ok, correct split
9 Correct 113 ms 12664 KB ok, correct split
10 Correct 72 ms 13040 KB ok, correct split
11 Correct 71 ms 13040 KB ok, correct split
12 Correct 73 ms 12944 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6520 KB ok, correct split
2 Correct 96 ms 12680 KB ok, correct split
3 Correct 36 ms 9080 KB ok, correct split
4 Correct 9 ms 6624 KB ok, correct split
5 Correct 117 ms 14648 KB ok, correct split
6 Correct 145 ms 14492 KB ok, correct split
7 Correct 136 ms 14328 KB ok, correct split
8 Correct 139 ms 15352 KB ok, correct split
9 Correct 127 ms 14148 KB ok, correct split
10 Correct 34 ms 8700 KB ok, no valid answer
11 Correct 49 ms 9564 KB ok, no valid answer
12 Correct 105 ms 12788 KB ok, no valid answer
13 Correct 97 ms 12536 KB ok, no valid answer
14 Correct 73 ms 12912 KB ok, no valid answer

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6520 KB ok, correct split
2 Correct 8 ms 6648 KB ok, no valid answer
3 Correct 7 ms 6520 KB ok, correct split
4 Correct 8 ms 6648 KB ok, correct split
5 Correct 8 ms 6524 KB ok, correct split
6 Correct 8 ms 6648 KB ok, correct split
7 Correct 10 ms 6648 KB ok, correct split
8 Correct 8 ms 6572 KB ok, correct split
9 Correct 10 ms 6776 KB ok, correct split
10 Correct 10 ms 6776 KB ok, correct split
11 Correct 8 ms 6648 KB ok, correct split
12 Correct 12 ms 6776 KB ok, correct split
13 Correct 10 ms 6692 KB ok, correct split
14 Correct 8 ms 6520 KB ok, correct split
15 Correct 8 ms 6648 KB ok, correct split
16 Correct 8 ms 6520 KB ok, correct split
17 Correct 8 ms 6648 KB ok, correct split
18 Correct 8 ms 6648 KB ok, correct split
19 Correct 8 ms 6648 KB ok, correct split
20 Correct 8 ms 6648 KB ok, correct split
21 Correct 10 ms 6776 KB ok, correct split
22 Correct 10 ms 6776 KB ok, correct split
23 Correct 11 ms 6776 KB ok, correct split
24 Correct 10 ms 6776 KB ok, correct split
25 Correct 11 ms 6776 KB ok, correct split
26 Correct 9 ms 6776 KB ok, correct split
27 Correct 10 ms 6776 KB ok, correct split
28 Correct 10 ms 6904 KB ok, correct split
29 Correct 11 ms 6724 KB ok, correct split
30 Correct 10 ms 6876 KB ok, correct split
31 Correct 8 ms 6648 KB ok, correct split
32 Correct 8 ms 6648 KB ok, correct split
33 Correct 8 ms 6648 KB ok, correct split
34 Correct 9 ms 6776 KB ok, correct split
35 Correct 10 ms 6776 KB ok, correct split
36 Correct 10 ms 6776 KB ok, correct split
37 Correct 10 ms 6904 KB ok, correct split
38 Correct 11 ms 6776 KB ok, correct split
39 Correct 10 ms 6904 KB ok, correct split
40 Correct 11 ms 6904 KB ok, correct split
41 Correct 9 ms 6776 KB ok, correct split
42 Correct 9 ms 6776 KB ok, correct split
43 Correct 10 ms 6904 KB ok, correct split
44 Correct 10 ms 6780 KB ok, correct split
45 Correct 10 ms 6776 KB ok, correct split
46 Correct 10 ms 6776 KB ok, correct split
47 Correct 10 ms 6776 KB ok, no valid answer
48 Correct 10 ms 6776 KB ok, correct split
49 Correct 10 ms 6776 KB ok, correct split
50 Correct 8 ms 6520 KB ok, no valid answer
51 Correct 8 ms 6648 KB ok, no valid answer
52 Correct 9 ms 6776 KB ok, no valid answer
53 Correct 12 ms 6776 KB ok, no valid answer
54 Correct 9 ms 6776 KB ok, no valid answer
55 Correct 10 ms 6776 KB ok, no valid answer
56 Correct 11 ms 6776 KB ok, no valid answer

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6648 KB ok, correct split
2 Correct 8 ms 6520 KB ok, correct split
3 Correct 7 ms 6524 KB ok, correct split
4 Correct 8 ms 6648 KB ok, correct split
5 Correct 8 ms 6648 KB ok, correct split
6 Correct 8 ms 6648 KB ok, correct split
7 Correct 122 ms 18552 KB ok, correct split
8 Correct 107 ms 16632 KB ok, correct split
9 Correct 120 ms 16120 KB ok, correct split
10 Correct 122 ms 18660 KB ok, correct split
11 Correct 111 ms 17528 KB ok, correct split
12 Correct 8 ms 6520 KB ok, correct split
13 Correct 8 ms 6648 KB ok, correct split
14 Correct 8 ms 6648 KB ok, correct split
15 Correct 108 ms 13384 KB ok, correct split
16 Correct 92 ms 12664 KB ok, correct split
17 Correct 123 ms 18424 KB ok, correct split
18 Correct 119 ms 16604 KB ok, correct split
19 Correct 119 ms 14020 KB ok, correct split
20 Correct 113 ms 12664 KB ok, correct split
21 Correct 72 ms 13040 KB ok, correct split
22 Correct 71 ms 13040 KB ok, correct split
23 Correct 73 ms 12944 KB ok, correct split
24 Correct 7 ms 6520 KB ok, correct split
25 Correct 96 ms 12680 KB ok, correct split
26 Correct 36 ms 9080 KB ok, correct split
27 Correct 9 ms 6624 KB ok, correct split
28 Correct 117 ms 14648 KB ok, correct split
29 Correct 145 ms 14492 KB ok, correct split
30 Correct 136 ms 14328 KB ok, correct split
31 Correct 139 ms 15352 KB ok, correct split
32 Correct 127 ms 14148 KB ok, correct split
33 Correct 34 ms 8700 KB ok, no valid answer
34 Correct 49 ms 9564 KB ok, no valid answer
35 Correct 105 ms 12788 KB ok, no valid answer
36 Correct 97 ms 12536 KB ok, no valid answer
37 Correct 73 ms 12912 KB ok, no valid answer
38 Correct 9 ms 6520 KB ok, correct split
39 Correct 8 ms 6648 KB ok, no valid answer
40 Correct 7 ms 6520 KB ok, correct split
41 Correct 8 ms 6648 KB ok, correct split
42 Correct 8 ms 6524 KB ok, correct split
43 Correct 8 ms 6648 KB ok, correct split
44 Correct 10 ms 6648 KB ok, correct split
45 Correct 8 ms 6572 KB ok, correct split
46 Correct 10 ms 6776 KB ok, correct split
47 Correct 10 ms 6776 KB ok, correct split
48 Correct 8 ms 6648 KB ok, correct split
49 Correct 12 ms 6776 KB ok, correct split
50 Correct 10 ms 6692 KB ok, correct split
51 Correct 8 ms 6520 KB ok, correct split
52 Correct 8 ms 6648 KB ok, correct split
53 Correct 8 ms 6520 KB ok, correct split
54 Correct 8 ms 6648 KB ok, correct split
55 Correct 8 ms 6648 KB ok, correct split
56 Correct 8 ms 6648 KB ok, correct split
57 Correct 8 ms 6648 KB ok, correct split
58 Correct 10 ms 6776 KB ok, correct split
59 Correct 10 ms 6776 KB ok, correct split
60 Correct 11 ms 6776 KB ok, correct split
61 Correct 10 ms 6776 KB ok, correct split
62 Correct 11 ms 6776 KB ok, correct split
63 Correct 9 ms 6776 KB ok, correct split
64 Correct 10 ms 6776 KB ok, correct split
65 Correct 10 ms 6904 KB ok, correct split
66 Correct 11 ms 6724 KB ok, correct split
67 Correct 10 ms 6876 KB ok, correct split
68 Correct 8 ms 6648 KB ok, correct split
69 Correct 8 ms 6648 KB ok, correct split
70 Correct 8 ms 6648 KB ok, correct split
71 Correct 9 ms 6776 KB ok, correct split
72 Correct 10 ms 6776 KB ok, correct split
73 Correct 10 ms 6776 KB ok, correct split
74 Correct 10 ms 6904 KB ok, correct split
75 Correct 11 ms 6776 KB ok, correct split
76 Correct 10 ms 6904 KB ok, correct split
77 Correct 11 ms 6904 KB ok, correct split
78 Correct 9 ms 6776 KB ok, correct split
79 Correct 9 ms 6776 KB ok, correct split
80 Correct 10 ms 6904 KB ok, correct split
81 Correct 10 ms 6780 KB ok, correct split
82 Correct 10 ms 6776 KB ok, correct split
83 Correct 10 ms 6776 KB ok, correct split
84 Correct 10 ms 6776 KB ok, no valid answer
85 Correct 10 ms 6776 KB ok, correct split
86 Correct 10 ms 6776 KB ok, correct split
87 Correct 8 ms 6520 KB ok, no valid answer
88 Correct 8 ms 6648 KB ok, no valid answer
89 Correct 9 ms 6776 KB ok, no valid answer
90 Correct 12 ms 6776 KB ok, no valid answer
91 Correct 9 ms 6776 KB ok, no valid answer
92 Correct 10 ms 6776 KB ok, no valid answer
93 Correct 11 ms 6776 KB ok, no valid answer
94 Correct 110 ms 14360 KB ok, correct split
95 Correct 128 ms 15992 KB ok, correct split
96 Correct 133 ms 15672 KB ok, correct split
97 Correct 38 ms 9464 KB ok, correct split
98 Correct 39 ms 9592 KB ok, correct split
99 Correct 51 ms 10588 KB ok, correct split
100 Correct 122 ms 15992 KB ok, correct split
101 Correct 109 ms 15736 KB ok, correct split
102 Correct 111 ms 15776 KB ok, correct split
103 Correct 108 ms 15604 KB ok, correct split
104 Correct 108 ms 16632 KB ok, correct split
105 Correct 57 ms 11256 KB ok, correct split
106 Correct 100 ms 16368 KB ok, correct split
107 Correct 96 ms 13816 KB ok, correct split
108 Correct 96 ms 13816 KB ok, correct split
109 Correct 143 ms 16236 KB ok, correct split
110 Correct 146 ms 16244 KB ok, correct split
111 Correct 136 ms 16372 KB ok, correct split
112 Correct 169 ms 16500 KB ok, correct split
113 Correct 138 ms 16504 KB ok, correct split
114 Correct 18 ms 7672 KB ok, correct split
115 Correct 18 ms 7672 KB ok, correct split
116 Correct 136 ms 16780 KB ok, correct split
117 Correct 120 ms 16500 KB ok, correct split
118 Correct 117 ms 13816 KB ok, correct split
119 Correct 153 ms 13792 KB ok, correct split
120 Correct 128 ms 16120 KB ok, correct split
121 Correct 104 ms 13672 KB ok, no valid answer
122 Correct 99 ms 13816 KB ok, no valid answer
123 Correct 144 ms 16444 KB ok, no valid answer
124 Correct 142 ms 15996 KB ok, no valid answer
125 Correct 91 ms 14836 KB ok, no valid answer
126 Correct 64 ms 13296 KB ok, no valid answer
127 Correct 105 ms 15184 KB ok, no valid answer