oj.uz

Submission #250045

# Submission time Handle Problem Language Result Execution time Memory
250045 2020-07-16T17:40:47 Z DavidDamian Split the Attractions (IOI19_split) C++14
18 / 100
 103 ms 13048 KB 
//#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> answer;
vector<int> adjList[100005];
int color[100005];
int cnt;
int A,B,C;
void dfs(int u)
{
    color[u]=1;
    answer[u]=2;
    cnt++;
    for(int v: adjList[u]){
        if(cnt<B){
            if(color[v]==0) dfs(v);
        }
    }
}
void dfs1(int u)
{
    color[u]=1;
    if(A){
        answer[u]=1;
        A--;
    }
    else if(B){
        answer[u]=2;
        B--;
    }
    else{
        answer[u]=3;
        C--;
    }
    for(int v: adjList[u]){
        if(color[v]==0)
            dfs1(v);
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m=p.size();
	answer.resize(n);
	A=a,B=b,C=c;
	for(int i=0;i<m;i++){
        adjList[ p[i] ].push_back(q[i]);
        adjList[ q[i] ].push_back(p[i]);
	}
	if(a==1){
        dfs(0);
        for(int i=0;i<n;i++){
            if(answer[i]==0){
                if(a){
                    a--;
                    answer[i]=1;
                }
                else answer[i]=3;
            }
        }
	}
	else{
        int root=0;
        for(int i=0;i<n;i++){
            if(adjList[i].size()==1){
                root=i;
                break;
            }
        }
        dfs1(root);
	}
	return answer;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 73 ms 12792 KB ok, correct split
8 Correct 72 ms 11768 KB ok, correct split
9 Correct 100 ms 12852 KB ok, correct split
10 Correct 68 ms 9336 KB ok, correct split
11 Correct 90 ms 12792 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 93 ms 11000 KB ok, correct split
5 Correct 73 ms 9848 KB ok, correct split
6 Correct 71 ms 9336 KB ok, correct split
7 Correct 68 ms 11240 KB ok, correct split
8 Correct 103 ms 13048 KB ok, correct split
9 Correct 64 ms 9720 KB ok, correct split
10 Correct 49 ms 9712 KB ok, correct split
11 Correct 53 ms 9712 KB ok, correct split
12 Correct 53 ms 10096 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Incorrect 63 ms 9848 KB 2 components are not connected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB 2 components are not connected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 73 ms 12792 KB ok, correct split
8 Correct 72 ms 11768 KB ok, correct split
9 Correct 100 ms 12852 KB ok, correct split
10 Correct 68 ms 9336 KB ok, correct split
11 Correct 90 ms 12792 KB ok, correct split
12 Correct 2 ms 2688 KB ok, correct split
13 Correct 2 ms 2688 KB ok, correct split
14 Correct 2 ms 2688 KB ok, correct split
15 Correct 93 ms 11000 KB ok, correct split
16 Correct 73 ms 9848 KB ok, correct split
17 Correct 71 ms 9336 KB ok, correct split
18 Correct 68 ms 11240 KB ok, correct split
19 Correct 103 ms 13048 KB ok, correct split
20 Correct 64 ms 9720 KB ok, correct split
21 Correct 49 ms 9712 KB ok, correct split
22 Correct 53 ms 9712 KB ok, correct split
23 Correct 53 ms 10096 KB ok, correct split
24 Correct 2 ms 2688 KB ok, correct split
25 Incorrect 63 ms 9848 KB 2 components are not connected
26 Halted 0 ms 0 KB -