oj.uz

Submission #167797

# Submission time Handle Problem Language Result Execution time Memory
167797 2019-12-10T07:37:26 Z oolimry Split the Attractions (IOI19_split) C++14
18 / 100
 237 ms 26008 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;

static vi answer;
static vi adj[100005];
static vi child[100005];
static vi tree[100005];
static int sz[100005];
static int p[100005];
static bool vis[100005];

class UFDS {
public:
    vi p, rak, setSize;
    int numSets;

    void create(int n){
        setSize.assign(n, 1);
        numSets = n;
        rak.assign(n, 0);
        p.assign(n, 0);
        for(int i =0;i < n;i++){
            p[i] = i;
        }
    }

    int findSet(int i){
        return (p[i] == i) ? i : (p[i] = findSet(p[i]));
    }

    bool isSameSet(int i, int j){
        return findSet(i) == findSet(j);
    }

    int unionSet(int i, int j){
        if(isSameSet(i,j))
            return 0;
        numSets--;
        int x = findSet(i);
        int y = findSet(j);

        if(rak[x] > rak[y]) {
            p[y] = x; setSize[x] += setSize[y];
        }

        else {
            p[x] = y; setSize[y] += setSize[x];
            if(rak[x] == rak[y]) rak[y]++;
        }
		return max(setSize[x],setSize[y]);
    }
};

void dfs(int u){
	vis[u] = true;
	sz[u] = 1;
	for(int v : adj[u]){
		if(!vis[v]){
			child[u].push_back(v);
			tree[u].push_back(v);
			tree[v].push_back(u);
			p[v] = u;
			dfs(v);
			sz[u] += sz[v];
		}	
	}
}

void bfs(int root, int number){
	if(number == 0) return;
	queue<int> bf;
	bf.push(root);
	while(!bf.empty()){
		int u = bf.front(); bf.pop();
		for(int v : tree[u]){
			if(answer[v] == 0){
				answer[v] = answer[u];
				number--;
				if(number == 0) return;
				bf.push(v);
			}
		}
	}
}
vi find_split(int n, int aaa, int bbb, int ccc, vi p, vi q) {
	vector<ii> v = {ii(aaa,1),ii(bbb,2),ii(ccc,3)};
	sort(v.begin(),v.end());
	int A = v[0].first;
	int B = v[1].first;
	int AColour = v[0].second;
	int BColour = v[1].second;
	int CColour = v[2].second;
	
	answer.assign(n,0);
	
	for(int i = 0;i < (int) p.size();i++){
		int x = p[i], y = q[i];
		adj[y].push_back(x);
		adj[x].push_back(y);
	}
	
	dfs(0);

	for(int i = 0;i < (int) p.size();i++){
		int x = p[i], y = q[i];
		if(sz[y] < sz[x]) swap(x,y); ///x is child of y
		
		int l = sz[x], r = n - sz[x];
		if(l > r) swap(l,r), swap(x,y);
		
		if(l >= A && r >= B){
			answer[x] = AColour;
			answer[y] = BColour;
			bfs(x,A-1);
			bfs(y,B-1);
			for(int i = 0;i < n;i++){
				if(answer[i] == 0) answer[i] = CColour;
			}
			return answer;
		}
	}
	
	int R = -1;
	for(int u = 0;u < n;u++){
		bool can = true;
		for(int v : tree[u]){
			if(sz[v] >= A){
				can = false;
				break;
			}
		}
		if(n - sz[u] >= A) can = false;
		if(can){
			R = u;
			break;
		}
	}
	
	
	UFDS uf;
	uf.create(n);
	for(int i = 0;i < (int) p.size();i++){
		int u = p[i]; int v = q[i];
		if(u == R || v == R) continue;
		if(p[u] == v || q[v] == u){
			uf.unionSet(u,v);
		}
	}
	
	for(int i = 0;i < (int) p.size();i++){
		int u = p[i]; int v = q[i];
		if(u == R || v == R) continue;
		if(p[u] == v || q[v] == u) continue;
			
		tree[u].push_back(v);
		tree[v].push_back(u);
		if(uf.unionSet(u,v) >= A){
			int x = u;
			int y = R;
			answer[x] = AColour;
			answer[y] = BColour;
			bfs(x,A-1);
			bfs(y,B-1);
			for(int i = 0;i < n;i++){
				if(answer[i] == 0) answer[i] = CColour;
			}
		}
	}
	
	return answer;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7388 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 8 ms 7288 KB ok, correct split
5 Correct 8 ms 7416 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 141 ms 25592 KB ok, correct split
8 Correct 138 ms 23800 KB ok, correct split
9 Correct 164 ms 23160 KB ok, correct split
10 Correct 142 ms 25848 KB ok, correct split
11 Correct 149 ms 26008 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7292 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 158 ms 22600 KB ok, correct split
5 Correct 127 ms 18424 KB ok, correct split
6 Correct 141 ms 25896 KB ok, correct split
7 Correct 144 ms 23544 KB ok, correct split
8 Correct 170 ms 20856 KB ok, correct split
9 Correct 133 ms 19704 KB ok, correct split
10 Correct 84 ms 17904 KB ok, correct split
11 Correct 89 ms 17796 KB ok, correct split
12 Correct 87 ms 17776 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 122 ms 18424 KB ok, correct split
3 Correct 46 ms 11768 KB ok, correct split
4 Correct 8 ms 7396 KB ok, correct split
5 Correct 139 ms 21624 KB ok, correct split
6 Correct 140 ms 21496 KB ok, correct split
7 Correct 143 ms 21496 KB ok, correct split
8 Correct 137 ms 22520 KB ok, correct split
9 Correct 138 ms 21240 KB ok, correct split
10 Incorrect 237 ms 11768 KB invalid split: #1=13744, #2=0, #3=19589
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7416 KB ok, no valid answer
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 8 ms 7416 KB ok, correct split
5 Correct 8 ms 7416 KB ok, correct split
6 Correct 8 ms 7288 KB ok, correct split
7 Correct 8 ms 7416 KB ok, correct split
8 Correct 8 ms 7416 KB ok, correct split
9 Correct 10 ms 7672 KB ok, correct split
10 Correct 10 ms 7672 KB ok, correct split
11 Correct 8 ms 7416 KB ok, correct split
12 Correct 11 ms 7672 KB ok, correct split
13 Correct 8 ms 7424 KB ok, correct split
14 Correct 8 ms 7416 KB ok, correct split
15 Correct 8 ms 7416 KB ok, correct split
16 Correct 9 ms 7416 KB ok, correct split
17 Correct 9 ms 7416 KB ok, correct split
18 Correct 8 ms 7416 KB ok, correct split
19 Correct 8 ms 7416 KB ok, correct split
20 Correct 9 ms 7548 KB ok, correct split
21 Correct 10 ms 7672 KB ok, correct split
22 Correct 10 ms 7672 KB ok, correct split
23 Correct 10 ms 7800 KB ok, correct split
24 Correct 10 ms 7800 KB ok, correct split
25 Correct 12 ms 7672 KB ok, correct split
26 Runtime error 26 ms 15736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB ok, correct split
2 Correct 8 ms 7388 KB ok, correct split
3 Correct 8 ms 7416 KB ok, correct split
4 Correct 8 ms 7288 KB ok, correct split
5 Correct 8 ms 7416 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 141 ms 25592 KB ok, correct split
8 Correct 138 ms 23800 KB ok, correct split
9 Correct 164 ms 23160 KB ok, correct split
10 Correct 142 ms 25848 KB ok, correct split
11 Correct 149 ms 26008 KB ok, correct split
12 Correct 8 ms 7292 KB ok, correct split
13 Correct 8 ms 7416 KB ok, correct split
14 Correct 8 ms 7416 KB ok, correct split
15 Correct 158 ms 22600 KB ok, correct split
16 Correct 127 ms 18424 KB ok, correct split
17 Correct 141 ms 25896 KB ok, correct split
18 Correct 144 ms 23544 KB ok, correct split
19 Correct 170 ms 20856 KB ok, correct split
20 Correct 133 ms 19704 KB ok, correct split
21 Correct 84 ms 17904 KB ok, correct split
22 Correct 89 ms 17796 KB ok, correct split
23 Correct 87 ms 17776 KB ok, correct split
24 Correct 8 ms 7416 KB ok, correct split
25 Correct 122 ms 18424 KB ok, correct split
26 Correct 46 ms 11768 KB ok, correct split
27 Correct 8 ms 7396 KB ok, correct split
28 Correct 139 ms 21624 KB ok, correct split
29 Correct 140 ms 21496 KB ok, correct split
30 Correct 143 ms 21496 KB ok, correct split
31 Correct 137 ms 22520 KB ok, correct split
32 Correct 138 ms 21240 KB ok, correct split
33 Incorrect 237 ms 11768 KB invalid split: #1=13744, #2=0, #3=19589
34 Halted 0 ms 0 KB -