oj.uz

Submission #147480

# Submission time Handle Problem Language Result Execution time Memory
147480 2019-08-29T16:36:48 Z mosiashvililuka Split the Attractions (IOI19_split) C++14
18 / 100
 116 ms 12724 KB 
#include<bits/stdc++.h>
using namespace std;
int z,x,d,e,ka[10],zx,m,la[100009];
vector <int> pas,v[100009];
bool bo[100009];
void dfs(int w){
	if(ka[zx]==0) return;
	bo[w]=1;
	pas[w]=zx;
	ka[zx]--;
	if(ka[zx]==0) return;
	for(vector <int>::iterator it=v[w].begin(); it!=v[w].end(); it++){
		if(bo[(*it)]==1) continue;
		dfs((*it));
		if(ka[zx]==0) return;
	}
}
void dfs2(int w){
	if(ka[zx]==0) return;
	bo[w]=1;
	pas[w]=zx;
	ka[zx]--;
	if(ka[zx]==0) return;
	for(vector <int>::iterator it=v[w].begin(); it!=v[w].end(); it++){
		if(bo[(*it)]==1) continue;
		dfs2((*it));
		if(ka[zx]==0) return;
	}
}
vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q){
	pas.resize(n);
	ka[1]=a;
	ka[2]=b;
	ka[3]=c;
	zx=0;
	m=p.size();
	for(int h=0; h<m; h++){
		v[p[h]].push_back(q[h]);
		v[q[h]].push_back(p[h]);
	}
	if(a!=1){
	zx=0;
	for(d=0; d<n; d++){
		if(v[d].size()!=1) continue;
		if(bo[d]==0){
			zx++;
			dfs(d);
		}
	}
	if(zx!=0){
	for(d=0; d<n; d++) if(pas[d]==0) pas[d]=3;
	}else{
	    zx=0;
	    for(d=0; d<n; d++){
	        if(bo[d]==0){
	            zx++;
	            dfs(d);
	            break;
	        }
	    }
	    for(d=0; d<n; d++){
	    	if(bo[d]==1){
	    		for(vector <int>::iterator it=v[d].begin(); it!=v[d].end(); it++){
					if(bo[(*it)]==1) continue;
					zx++;
					dfs((*it));
					break;
				}
				if(zx==2) break;
			}
		}
		for(d=0; d<n; d++){
	        if(bo[d]==0){
	            zx++;
	            dfs(d);
	            break;
	        }
	    }
	}
	}else{
		zx=2;
		dfs2(0);
		for(d=0; d<n; d++){
			if(pas[d]==0){pas[d]=1;break;}
		}
		for(d=0; d<n; d++) if(pas[d]==0) pas[d]=3;
	}
	return pas;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 78 ms 9336 KB ok, correct split
8 Correct 88 ms 10360 KB ok, correct split
9 Correct 103 ms 9848 KB ok, correct split
10 Correct 77 ms 8184 KB ok, correct split
11 Correct 83 ms 9336 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 101 ms 9356 KB ok, correct split
5 Correct 78 ms 8440 KB ok, correct split
6 Correct 72 ms 9336 KB ok, correct split
7 Correct 78 ms 11000 KB ok, correct split
8 Correct 116 ms 12724 KB ok, correct split
9 Correct 74 ms 9464 KB ok, correct split
10 Correct 61 ms 9456 KB ok, correct split
11 Correct 64 ms 9456 KB ok, correct split
12 Correct 66 ms 9840 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Runtime error 88 ms 12412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB invalid split: #1=4, #2=1, #3=4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 78 ms 9336 KB ok, correct split
8 Correct 88 ms 10360 KB ok, correct split
9 Correct 103 ms 9848 KB ok, correct split
10 Correct 77 ms 8184 KB ok, correct split
11 Correct 83 ms 9336 KB ok, correct split
12 Correct 4 ms 2680 KB ok, correct split
13 Correct 4 ms 2680 KB ok, correct split
14 Correct 4 ms 2680 KB ok, correct split
15 Correct 101 ms 9356 KB ok, correct split
16 Correct 78 ms 8440 KB ok, correct split
17 Correct 72 ms 9336 KB ok, correct split
18 Correct 78 ms 11000 KB ok, correct split
19 Correct 116 ms 12724 KB ok, correct split
20 Correct 74 ms 9464 KB ok, correct split
21 Correct 61 ms 9456 KB ok, correct split
22 Correct 64 ms 9456 KB ok, correct split
23 Correct 66 ms 9840 KB ok, correct split
24 Correct 4 ms 2680 KB ok, correct split
25 Runtime error 88 ms 12412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -