oj.uz

Submission #153128

# Submission time Handle Problem Language Result Execution time Memory
153128 2019-09-12T14:19:45 Z errorgorn Split the Attractions (IOI19_split) C++14
18 / 100
 124 ms 10476 KB 
#include "split.h"
#include <cstdio>
#include <vector>
using namespace std;
vector<int> al[100005];
int color,num;
vector<int> res;
void dfs(int i){
    res[i]=color;
    num--;
    if (!num) return;
    for (vector<int>::iterator it=al[i].begin();it!=al[i].end();it++){
        if (!res[*it]) dfs(*it);
        if (!num) return;
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    res=vector<int> (n,0);
	for (int x=0;x<p.size();x++){
        al[p[x]].push_back(q[x]);
        al[q[x]].push_back(p[x]);
	}
    if (a==1){
        if (b>c) num=c,color=3;
        else num=b,color=2;
        dfs(0);
        color=(color==2)?3:2;
        bool lone=true;
        for (int x=0;x<n;x++){
            if (!res[x]){
                if (lone){
                    lone=false;
                    res[x]=1;
                }
                else{
                    res[x]=color;
                }
            }
        }
    }
    else{
        int pos=0;
        for (int x=0;x<n;x++){
            if (al[x].size()==1){
                pos=x;
                break;
            }
        }
        while (a--){
            res[pos]=1;
            if (res[al[pos][0]]==0) pos=al[pos][0];
            else pos=al[pos][1];
        }
        while (b--){
            res[pos]=2;
            if (res[al[pos][0]]==0) pos=al[pos][0];
            else pos=al[pos][1];
        }
        for (int x=0;x<n;x++) if (res[x]==0) res[x]=3;
    }
    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:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<p.size();x++){
               ~^~~~~~~~~

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 5 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 96 ms 9336 KB ok, correct split
8 Correct 78 ms 9336 KB ok, correct split
9 Correct 88 ms 9340 KB ok, correct split
10 Correct 77 ms 9268 KB ok, correct split
11 Correct 96 ms 9392 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB ok, correct split
2 Correct 5 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 104 ms 9260 KB ok, correct split
5 Correct 77 ms 8216 KB ok, correct split
6 Correct 75 ms 8160 KB ok, correct split
7 Correct 83 ms 9720 KB ok, correct split
8 Correct 124 ms 10476 KB ok, correct split
9 Correct 76 ms 8184 KB ok, correct split
10 Correct 64 ms 8560 KB ok, correct split
11 Correct 62 ms 8472 KB ok, correct split
12 Correct 67 ms 8560 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 Incorrect 80 ms 9464 KB invalid split: #1=7, #2=2, #3=99991
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=3, #2=2, #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 5 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 96 ms 9336 KB ok, correct split
8 Correct 78 ms 9336 KB ok, correct split
9 Correct 88 ms 9340 KB ok, correct split
10 Correct 77 ms 9268 KB ok, correct split
11 Correct 96 ms 9392 KB ok, correct split
12 Correct 5 ms 2680 KB ok, correct split
13 Correct 5 ms 2680 KB ok, correct split
14 Correct 4 ms 2680 KB ok, correct split
15 Correct 104 ms 9260 KB ok, correct split
16 Correct 77 ms 8216 KB ok, correct split
17 Correct 75 ms 8160 KB ok, correct split
18 Correct 83 ms 9720 KB ok, correct split
19 Correct 124 ms 10476 KB ok, correct split
20 Correct 76 ms 8184 KB ok, correct split
21 Correct 64 ms 8560 KB ok, correct split
22 Correct 62 ms 8472 KB ok, correct split
23 Correct 67 ms 8560 KB ok, correct split
24 Correct 4 ms 2680 KB ok, correct split
25 Incorrect 80 ms 9464 KB invalid split: #1=7, #2=2, #3=99991
26 Halted 0 ms 0 KB -