oj.uz

Submission #520985

# Submission time Handle Problem Language Result Execution time Memory
520985 2022-01-31T15:21:07 Z nadorbenedek Split the Attractions (IOI19_split) C++14
18 / 100
 90 ms 12256 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int> > adj;

void dfs(int v, vector<int> &res, int &noch, int id){
    if(noch == 0){
        return;
    }
    res[v] = id;
    noch--;
    for(int edge : adj[v]){
        if(!res[edge]){
            dfs(edge, res, noch, id);
        }
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res(n, 0);
	vector<pair<int, int> > z = {{a, 1}, {b, 2}, {c, 3}};
	sort(z.begin(), z.end());
	adj.resize(n);
	for(int i = 0; i < p.size(); i++){
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
	}
	int root = 0;
	for(int i = 0; i < n; i++){
        if(adj[i].size() == 1){
            root = i;
            break;
        }
	}
	dfs(root, res, z[1].first, z[1].second);
	for(int i = 0; i < n; i++){
        if(res[i] == 0){
            root = i;
            break;
        }
	}
    dfs(root, res, z[0].first, z[0].second);
    for(int i = 0; i < n; i++){
        if(res[i] == 0){
            res[i] = z[2].second;
        }
    }
	return res;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 0; i < p.size(); i++){
      |                 ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB ok, correct split
2 Correct 0 ms 204 KB ok, correct split
3 Correct 0 ms 204 KB ok, correct split
4 Correct 1 ms 204 KB ok, correct split
5 Correct 0 ms 204 KB ok, correct split
6 Correct 0 ms 204 KB ok, correct split
7 Correct 45 ms 10392 KB ok, correct split
8 Correct 90 ms 8772 KB ok, correct split
9 Correct 48 ms 11160 KB ok, correct split
10 Correct 41 ms 8856 KB ok, correct split
11 Correct 47 ms 10392 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB ok, correct split
2 Correct 1 ms 204 KB ok, correct split
3 Correct 1 ms 204 KB ok, correct split
4 Correct 56 ms 8744 KB ok, correct split
5 Correct 42 ms 7732 KB ok, correct split
6 Correct 50 ms 8856 KB ok, correct split
7 Correct 54 ms 11164 KB ok, correct split
8 Correct 75 ms 12256 KB ok, correct split
9 Correct 85 ms 8860 KB ok, correct split
10 Correct 84 ms 8892 KB ok, correct split
11 Correct 44 ms 8760 KB ok, correct split
12 Correct 43 ms 9276 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB ok, correct split
2 Incorrect 48 ms 8144 KB invalid split: #1=1955, #2=40000, #3=58045
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB ok, correct split
2 Incorrect 1 ms 208 KB invalid split: #1=1, #2=2, #3=3
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB ok, correct split
2 Correct 0 ms 204 KB ok, correct split
3 Correct 0 ms 204 KB ok, correct split
4 Correct 1 ms 204 KB ok, correct split
5 Correct 0 ms 204 KB ok, correct split
6 Correct 0 ms 204 KB ok, correct split
7 Correct 45 ms 10392 KB ok, correct split
8 Correct 90 ms 8772 KB ok, correct split
9 Correct 48 ms 11160 KB ok, correct split
10 Correct 41 ms 8856 KB ok, correct split
11 Correct 47 ms 10392 KB ok, correct split
12 Correct 1 ms 204 KB ok, correct split
13 Correct 1 ms 204 KB ok, correct split
14 Correct 1 ms 204 KB ok, correct split
15 Correct 56 ms 8744 KB ok, correct split
16 Correct 42 ms 7732 KB ok, correct split
17 Correct 50 ms 8856 KB ok, correct split
18 Correct 54 ms 11164 KB ok, correct split
19 Correct 75 ms 12256 KB ok, correct split
20 Correct 85 ms 8860 KB ok, correct split
21 Correct 84 ms 8892 KB ok, correct split
22 Correct 44 ms 8760 KB ok, correct split
23 Correct 43 ms 9276 KB ok, correct split
24 Correct 0 ms 204 KB ok, correct split
25 Incorrect 48 ms 8144 KB invalid split: #1=1955, #2=40000, #3=58045
26 Halted 0 ms 0 KB -