oj.uz

Submission #167799

# Submission time Handle Problem Language Result Execution time Memory
167799 2019-12-10T07:40:22 Z oolimry Split the Attractions (IOI19_split) C++14
18 / 100
 182 ms 26348 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 pa[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);
			pa[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;
		}
	}
	
	assert(R != -1);
	
	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(pa[u] == v || pa[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(pa[u] == v || pa[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 7420 KB ok, correct split
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 7416 KB ok, correct split
7 Correct 159 ms 25988 KB ok, correct split
8 Correct 138 ms 24184 KB ok, correct split
9 Correct 148 ms 23516 KB ok, correct split
10 Correct 157 ms 26224 KB ok, correct split
11 Correct 153 ms 26348 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7288 KB ok, correct split
2 Correct 8 ms 7416 KB ok, correct split
3 Correct 8 ms 7288 KB ok, correct split
4 Correct 161 ms 23004 KB ok, correct split
5 Correct 139 ms 18812 KB ok, correct split
6 Correct 160 ms 26232 KB ok, correct split
7 Correct 147 ms 23928 KB ok, correct split
8 Correct 182 ms 21240 KB ok, correct split
9 Correct 146 ms 20088 KB ok, correct split
10 Correct 92 ms 18288 KB ok, correct split
11 Correct 93 ms 18288 KB ok, correct split
12 Correct 95 ms 18288 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7288 KB ok, correct split
2 Correct 131 ms 18808 KB ok, correct split
3 Correct 47 ms 11896 KB ok, correct split
4 Correct 8 ms 7416 KB ok, correct split
5 Correct 147 ms 22108 KB ok, correct split
6 Correct 144 ms 21812 KB ok, correct split
7 Correct 141 ms 21752 KB ok, correct split
8 Correct 152 ms 22776 KB ok, correct split
9 Correct 154 ms 21624 KB ok, correct split
10 Runtime error 46 ms 22264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 10 ms 7416 KB ok, correct split
5 Correct 8 ms 7288 KB ok, correct split
6 Correct 8 ms 7416 KB ok, correct split
7 Correct 9 ms 7416 KB ok, correct split
8 Correct 9 ms 7388 KB ok, correct split
9 Correct 13 ms 7772 KB ok, correct split
10 Correct 11 ms 7672 KB ok, correct split
11 Correct 10 ms 7416 KB ok, correct split
12 Correct 13 ms 7800 KB ok, correct split
13 Correct 10 ms 7416 KB ok, correct split
14 Correct 9 ms 7416 KB ok, correct split
15 Correct 9 ms 7420 KB ok, correct split
16 Correct 8 ms 7416 KB ok, correct split
17 Correct 10 ms 7416 KB ok, correct split
18 Correct 10 ms 7416 KB ok, correct split
19 Correct 8 ms 7416 KB ok, correct split
20 Correct 11 ms 7544 KB ok, correct split
21 Correct 12 ms 7800 KB ok, correct split
22 Correct 13 ms 7800 KB ok, correct split
23 Correct 12 ms 7800 KB ok, correct split
24 Correct 10 ms 7800 KB ok, correct split
25 Correct 10 ms 7672 KB ok, correct split
26 Runtime error 20 ms 15452 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 7420 KB ok, correct split
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 7416 KB ok, correct split
7 Correct 159 ms 25988 KB ok, correct split
8 Correct 138 ms 24184 KB ok, correct split
9 Correct 148 ms 23516 KB ok, correct split
10 Correct 157 ms 26224 KB ok, correct split
11 Correct 153 ms 26348 KB ok, correct split
12 Correct 8 ms 7288 KB ok, correct split
13 Correct 8 ms 7416 KB ok, correct split
14 Correct 8 ms 7288 KB ok, correct split
15 Correct 161 ms 23004 KB ok, correct split
16 Correct 139 ms 18812 KB ok, correct split
17 Correct 160 ms 26232 KB ok, correct split
18 Correct 147 ms 23928 KB ok, correct split
19 Correct 182 ms 21240 KB ok, correct split
20 Correct 146 ms 20088 KB ok, correct split
21 Correct 92 ms 18288 KB ok, correct split
22 Correct 93 ms 18288 KB ok, correct split
23 Correct 95 ms 18288 KB ok, correct split
24 Correct 8 ms 7288 KB ok, correct split
25 Correct 131 ms 18808 KB ok, correct split
26 Correct 47 ms 11896 KB ok, correct split
27 Correct 8 ms 7416 KB ok, correct split
28 Correct 147 ms 22108 KB ok, correct split
29 Correct 144 ms 21812 KB ok, correct split
30 Correct 141 ms 21752 KB ok, correct split
31 Correct 152 ms 22776 KB ok, correct split
32 Correct 154 ms 21624 KB ok, correct split
33 Runtime error 46 ms 22264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -