oj.uz

Submission #346009

# Submission time Handle Problem Language Result Execution time Memory
346009 2021-01-08T22:42:18 Z AmineWeslati Split the Attractions (IOI19_split) C++14
100 / 100
 193 ms 33076 KB 
//Never stop trying
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e9;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}

#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

#ifndef LOCAL
#include "split.h"
#endif

int N,A,B;  //A<=B<=C
vi order,ans(MX);
vpi ed;

vi vec;
bool cmp(int i, int j){
	return vec[i] < vec[j];
}
void reorder(int a, int b, int c){
	vec.assign({0,a,b,c});
	order.assign({0,1,2,3});
	sort(all(order),cmp);
	A=vec[order[1]],B=vec[order[2]];
}

vi par(MX),rnk(MX);
int findSet(int u){ return par[u]==u ? u : par[u]=findSet(par[u]); }
void unionSet(int u, int v){
	u=findSet(u),v=findSet(v);
	if(rnk[v]>rnk[u]) swap(u,v);
	if(rnk[v]==rnk[u]) rnk[u]++;
	par[v]=u;
}

vi adj[MX],sub(MX);
void dfs(int u, int p){
	sub[u]=1;
	for(auto v: adj[u]) if(v!=p){
		dfs(v,u);
		sub[u]+=sub[v];
	}
}

int r;
void color(int u, int p, int c, int no){
	ans[u]=c;
	r--;
	for(auto v: adj[u]) if(v!=p && v!=no && r>0){
		color(v,u,c,no);
	}
}


vi adj2[MX],adj3[MX],W(MX),CC(MX);
void assignComp(int u, int p, int idx){
	CC[u]=idx;
	for(auto v: adj[u]) if(v!=p){
		adj2[u].pb(v);
		adj2[v].pb(u);
		assignComp(v,u,idx);
	}
}

vi colored,vis(MX);
void color2(int u){
	vis[u]=1;
	colored.pb(u);
	r-=W[u];
	for(auto v: adj3[u]) if(!vis[v] && r>0){
		color2(v);
	}
}

bool chosen[MX];
void color3(int u){
	ans[u]=1;
	r--;
	for(auto v: adj2[u]) if(ans[v]==0 && chosen[CC[v]] && r>0){
		color3(v);
	}
}

void color4(int u, int p){
	ans[u]=2;
	r--;
	for(auto v: adj[u]) if(v!=p && ans[v]==0 && r>0) color4(v,u);
}


vi find_split(int n, int aa, int bb, int cc, vi p, vi q){
	N=n; ans.assign(N,0);
	reorder(aa,bb,cc);

	FOR(i,0,N) par[i]=i,rnk[i]=0;
	FOR(i,0,sz(p)){
		int u=p[i],v=q[i];
		if(findSet(u)!=findSet(v)){
			unionSet(u,v);
			adj[u].pb(v); 
			adj[v].pb(u);
		}
		else ed.eb(u,v);
	}


	dfs(0,0);
	int C; 
	FOR(u,0,N){
		bool y=true;
		y&=(N-sub[u]<=N/2);
		for(auto v: adj[u]) if(sub[v]<sub[u]) y&=(sub[v]<=N/2);
		if(y){
			C=u; break;
		}
	}

	dfs(C,C);
	int c=-1; for(auto v: adj[C]) if(sub[v]>=A) c=v;

	if(c!=-1){
		r=A;
		color(c,C,1,-1);
		r=B;
		color(C,C,2,c);
	}
	else{
		int cnt=-1,head[N];
		for(auto ch: adj[C]){
			cnt++;
			W[cnt]=sub[ch];
			head[cnt]=ch;
			assignComp(ch,C,cnt);
		}

		for(auto x: ed){
			int u=x.fi,v=x.se;
			if(u==C || v==C) continue;
			adj2[u].pb(v); adj2[v].pb(u);
			u=CC[u],v=CC[v];
			if(u==v) continue;
			adj3[u].pb(v); adj3[v].pb(u);
		}

		FOR(i,0,cnt+1) vis[i]=0;
		bool done=false;
		FOR(i,0,cnt+1) if(vis[i]==0){
			r=A;
			colored.clear();
			color2(i);

			if(r<=0){
				done=true;
				
				memset(chosen,0,sizeof(chosen));
				for(auto x: colored) chosen[x]=true;
				r=A;
				color3(head[colored[0]]);
				break;
			}
		}

		if(!done) return vi(N,0);
		r=B;
		color4(C,C);
		assert(r<=0);
	}

	FOR(i,0,N) if(ans[i]==0) ans[i]=3;
	FOR(i,0,N) ans[i]=order[ans[i]]; 
	return ans;
}


#ifdef LOCAL
int main() {
    boost; IO();

    int N,M,a,b,c; cin>>N>>M>>a>>b>>c;
    vi p(M),q(M);
    FOR(i,0,M) cin>>p[i]>>q[i];
    /*FOR(i,0,M) cin>>p[i];
    FOR(i,0,M) cin>>q[i];*/
    vi v=find_split(N,a,b,c,p,q);
    for(auto x: v) cout << x << ' '; cout << endl;

    return 0;
}
#endif

/*
9 10 4 2 3
0 0 0 0 0 0 1 3 4 5
1 2 3 4 6 8 7 7 5 6
*/

/*

12 12 4 4 4
0 1
0 4
0 6
0 9
1 2
1 3
4 5
6 7 
6 8
9 10 
9 11
3 5
*/


/* Careful!!!
    .Array bounds
    .Infinite loops
    .Uninitialized variables / empty containers
    .Multisets are shit

   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
*/

Compilation message

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:165:6: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
  165 |  int C;
      |      ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19948 KB ok, correct split
2 Correct 13 ms 19948 KB ok, correct split
3 Correct 13 ms 19948 KB ok, correct split
4 Correct 13 ms 19948 KB ok, correct split
5 Correct 13 ms 19948 KB ok, correct split
6 Correct 12 ms 19948 KB ok, correct split
7 Correct 127 ms 31060 KB ok, correct split
8 Correct 118 ms 29164 KB ok, correct split
9 Correct 129 ms 28652 KB ok, correct split
10 Correct 112 ms 30956 KB ok, correct split
11 Correct 124 ms 30060 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19948 KB ok, correct split
2 Correct 13 ms 19948 KB ok, correct split
3 Correct 13 ms 19948 KB ok, correct split
4 Correct 110 ms 26212 KB ok, correct split
5 Correct 102 ms 25068 KB ok, correct split
6 Correct 116 ms 30956 KB ok, correct split
7 Correct 133 ms 29036 KB ok, correct split
8 Correct 130 ms 27232 KB ok, correct split
9 Correct 105 ms 25068 KB ok, correct split
10 Correct 67 ms 25444 KB ok, correct split
11 Correct 66 ms 25444 KB ok, correct split
12 Correct 69 ms 25444 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19948 KB ok, correct split
2 Correct 104 ms 25068 KB ok, correct split
3 Correct 39 ms 21996 KB ok, correct split
4 Correct 13 ms 19948 KB ok, correct split
5 Correct 117 ms 27116 KB ok, correct split
6 Correct 121 ms 26928 KB ok, correct split
7 Correct 123 ms 27024 KB ok, correct split
8 Correct 119 ms 27884 KB ok, correct split
9 Correct 124 ms 26860 KB ok, correct split
10 Correct 42 ms 22764 KB ok, no valid answer
11 Correct 60 ms 24172 KB ok, no valid answer
12 Correct 101 ms 26856 KB ok, no valid answer
13 Correct 135 ms 28140 KB ok, no valid answer
14 Correct 75 ms 25828 KB ok, no valid answer

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19948 KB ok, correct split
2 Correct 12 ms 19948 KB ok, no valid answer
3 Correct 13 ms 19948 KB ok, correct split
4 Correct 13 ms 19948 KB ok, correct split
5 Correct 13 ms 19948 KB ok, correct split
6 Correct 13 ms 19948 KB ok, correct split
7 Correct 13 ms 19948 KB ok, correct split
8 Correct 13 ms 19948 KB ok, correct split
9 Correct 15 ms 20076 KB ok, correct split
10 Correct 15 ms 20076 KB ok, correct split
11 Correct 13 ms 19948 KB ok, correct split
12 Correct 16 ms 20460 KB ok, correct split
13 Correct 13 ms 19968 KB ok, correct split
14 Correct 13 ms 19948 KB ok, correct split
15 Correct 13 ms 19948 KB ok, correct split
16 Correct 13 ms 19948 KB ok, correct split
17 Correct 13 ms 19948 KB ok, correct split
18 Correct 13 ms 19948 KB ok, correct split
19 Correct 13 ms 19948 KB ok, correct split
20 Correct 14 ms 19948 KB ok, correct split
21 Correct 14 ms 20076 KB ok, correct split
22 Correct 15 ms 20076 KB ok, correct split
23 Correct 14 ms 20096 KB ok, correct split
24 Correct 14 ms 20220 KB ok, correct split
25 Correct 14 ms 20076 KB ok, correct split
26 Correct 15 ms 20076 KB ok, correct split
27 Correct 15 ms 20076 KB ok, correct split
28 Correct 14 ms 20076 KB ok, correct split
29 Correct 13 ms 19948 KB ok, correct split
30 Correct 14 ms 20076 KB ok, correct split
31 Correct 13 ms 19948 KB ok, correct split
32 Correct 13 ms 19948 KB ok, correct split
33 Correct 13 ms 19948 KB ok, correct split
34 Correct 14 ms 20076 KB ok, correct split
35 Correct 14 ms 20076 KB ok, correct split
36 Correct 14 ms 20076 KB ok, correct split
37 Correct 16 ms 20460 KB ok, correct split
38 Correct 15 ms 20460 KB ok, correct split
39 Correct 15 ms 20480 KB ok, correct split
40 Correct 15 ms 20460 KB ok, correct split
41 Correct 14 ms 20204 KB ok, correct split
42 Correct 14 ms 20224 KB ok, correct split
43 Correct 15 ms 20076 KB ok, correct split
44 Correct 15 ms 20076 KB ok, correct split
45 Correct 14 ms 20076 KB ok, correct split
46 Correct 14 ms 20076 KB ok, correct split
47 Correct 15 ms 20204 KB ok, no valid answer
48 Correct 14 ms 20076 KB ok, correct split
49 Correct 15 ms 20332 KB ok, correct split
50 Correct 13 ms 19948 KB ok, no valid answer
51 Correct 13 ms 19948 KB ok, no valid answer
52 Correct 14 ms 20076 KB ok, no valid answer
53 Correct 15 ms 20204 KB ok, no valid answer
54 Correct 14 ms 20076 KB ok, no valid answer
55 Correct 15 ms 20204 KB ok, no valid answer
56 Correct 14 ms 20204 KB ok, no valid answer

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19948 KB ok, correct split
2 Correct 13 ms 19948 KB ok, correct split
3 Correct 13 ms 19948 KB ok, correct split
4 Correct 13 ms 19948 KB ok, correct split
5 Correct 13 ms 19948 KB ok, correct split
6 Correct 12 ms 19948 KB ok, correct split
7 Correct 127 ms 31060 KB ok, correct split
8 Correct 118 ms 29164 KB ok, correct split
9 Correct 129 ms 28652 KB ok, correct split
10 Correct 112 ms 30956 KB ok, correct split
11 Correct 124 ms 30060 KB ok, correct split
12 Correct 13 ms 19948 KB ok, correct split
13 Correct 13 ms 19948 KB ok, correct split
14 Correct 13 ms 19948 KB ok, correct split
15 Correct 110 ms 26212 KB ok, correct split
16 Correct 102 ms 25068 KB ok, correct split
17 Correct 116 ms 30956 KB ok, correct split
18 Correct 133 ms 29036 KB ok, correct split
19 Correct 130 ms 27232 KB ok, correct split
20 Correct 105 ms 25068 KB ok, correct split
21 Correct 67 ms 25444 KB ok, correct split
22 Correct 66 ms 25444 KB ok, correct split
23 Correct 69 ms 25444 KB ok, correct split
24 Correct 12 ms 19948 KB ok, correct split
25 Correct 104 ms 25068 KB ok, correct split
26 Correct 39 ms 21996 KB ok, correct split
27 Correct 13 ms 19948 KB ok, correct split
28 Correct 117 ms 27116 KB ok, correct split
29 Correct 121 ms 26928 KB ok, correct split
30 Correct 123 ms 27024 KB ok, correct split
31 Correct 119 ms 27884 KB ok, correct split
32 Correct 124 ms 26860 KB ok, correct split
33 Correct 42 ms 22764 KB ok, no valid answer
34 Correct 60 ms 24172 KB ok, no valid answer
35 Correct 101 ms 26856 KB ok, no valid answer
36 Correct 135 ms 28140 KB ok, no valid answer
37 Correct 75 ms 25828 KB ok, no valid answer
38 Correct 12 ms 19948 KB ok, correct split
39 Correct 12 ms 19948 KB ok, no valid answer
40 Correct 13 ms 19948 KB ok, correct split
41 Correct 13 ms 19948 KB ok, correct split
42 Correct 13 ms 19948 KB ok, correct split
43 Correct 13 ms 19948 KB ok, correct split
44 Correct 13 ms 19948 KB ok, correct split
45 Correct 13 ms 19948 KB ok, correct split
46 Correct 15 ms 20076 KB ok, correct split
47 Correct 15 ms 20076 KB ok, correct split
48 Correct 13 ms 19948 KB ok, correct split
49 Correct 16 ms 20460 KB ok, correct split
50 Correct 13 ms 19968 KB ok, correct split
51 Correct 13 ms 19948 KB ok, correct split
52 Correct 13 ms 19948 KB ok, correct split
53 Correct 13 ms 19948 KB ok, correct split
54 Correct 13 ms 19948 KB ok, correct split
55 Correct 13 ms 19948 KB ok, correct split
56 Correct 13 ms 19948 KB ok, correct split
57 Correct 14 ms 19948 KB ok, correct split
58 Correct 14 ms 20076 KB ok, correct split
59 Correct 15 ms 20076 KB ok, correct split
60 Correct 14 ms 20096 KB ok, correct split
61 Correct 14 ms 20220 KB ok, correct split
62 Correct 14 ms 20076 KB ok, correct split
63 Correct 15 ms 20076 KB ok, correct split
64 Correct 15 ms 20076 KB ok, correct split
65 Correct 14 ms 20076 KB ok, correct split
66 Correct 13 ms 19948 KB ok, correct split
67 Correct 14 ms 20076 KB ok, correct split
68 Correct 13 ms 19948 KB ok, correct split
69 Correct 13 ms 19948 KB ok, correct split
70 Correct 13 ms 19948 KB ok, correct split
71 Correct 14 ms 20076 KB ok, correct split
72 Correct 14 ms 20076 KB ok, correct split
73 Correct 14 ms 20076 KB ok, correct split
74 Correct 16 ms 20460 KB ok, correct split
75 Correct 15 ms 20460 KB ok, correct split
76 Correct 15 ms 20480 KB ok, correct split
77 Correct 15 ms 20460 KB ok, correct split
78 Correct 14 ms 20204 KB ok, correct split
79 Correct 14 ms 20224 KB ok, correct split
80 Correct 15 ms 20076 KB ok, correct split
81 Correct 15 ms 20076 KB ok, correct split
82 Correct 14 ms 20076 KB ok, correct split
83 Correct 14 ms 20076 KB ok, correct split
84 Correct 15 ms 20204 KB ok, no valid answer
85 Correct 14 ms 20076 KB ok, correct split
86 Correct 15 ms 20332 KB ok, correct split
87 Correct 13 ms 19948 KB ok, no valid answer
88 Correct 13 ms 19948 KB ok, no valid answer
89 Correct 14 ms 20076 KB ok, no valid answer
90 Correct 15 ms 20204 KB ok, no valid answer
91 Correct 14 ms 20076 KB ok, no valid answer
92 Correct 15 ms 20204 KB ok, no valid answer
93 Correct 14 ms 20204 KB ok, no valid answer
94 Correct 106 ms 25704 KB ok, correct split
95 Correct 136 ms 27360 KB ok, correct split
96 Correct 191 ms 31968 KB ok, correct split
97 Correct 40 ms 21996 KB ok, correct split
98 Correct 41 ms 22124 KB ok, correct split
99 Correct 51 ms 23396 KB ok, correct split
100 Correct 125 ms 27488 KB ok, correct split
101 Correct 128 ms 26852 KB ok, correct split
102 Correct 149 ms 31840 KB ok, correct split
103 Correct 145 ms 31460 KB ok, correct split
104 Correct 107 ms 28132 KB ok, correct split
105 Correct 63 ms 23148 KB ok, correct split
106 Correct 103 ms 27788 KB ok, correct split
107 Correct 100 ms 25068 KB ok, correct split
108 Correct 102 ms 25068 KB ok, correct split
109 Correct 139 ms 27280 KB ok, correct split
110 Correct 186 ms 32736 KB ok, correct split
111 Correct 184 ms 32736 KB ok, correct split
112 Correct 178 ms 32992 KB ok, correct split
113 Correct 180 ms 33076 KB ok, correct split
114 Correct 25 ms 21484 KB ok, correct split
115 Correct 24 ms 21484 KB ok, correct split
116 Correct 112 ms 27488 KB ok, correct split
117 Correct 117 ms 27616 KB ok, correct split
118 Correct 115 ms 25068 KB ok, correct split
119 Correct 151 ms 28652 KB ok, correct split
120 Correct 161 ms 30828 KB ok, correct split
121 Correct 138 ms 28360 KB ok, no valid answer
122 Correct 125 ms 27884 KB ok, no valid answer
123 Correct 192 ms 31840 KB ok, no valid answer
124 Correct 193 ms 31712 KB ok, no valid answer
125 Correct 110 ms 28388 KB ok, no valid answer
126 Correct 64 ms 25188 KB ok, no valid answer
127 Correct 126 ms 30944 KB ok, no valid answer