oj.uz

Submission #153125

# Submission time Handle Problem Language Result Execution time Memory
153125 2019-09-12T14:17:45 Z errorgorn Split the Attractions (IOI19_split) C++14
11 / 100
 131 ms 10756 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=res[al[pos][1]];
            else pos=res[al[pos][1]];
        }
        while (b--){
            res[pos]=2;
            if (res[al[pos][0]]==0) pos=res[al[pos][1]];
            else pos=res[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
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 Incorrect 4 ms 2680 KB invalid split: #1=0, #2=1, #3=3
5 Halted 0 ms 0 KB -

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 5 ms 2680 KB ok, correct split
4 Correct 97 ms 9524 KB ok, correct split
5 Correct 80 ms 8572 KB ok, correct split
6 Correct 77 ms 8388 KB ok, correct split
7 Correct 78 ms 9884 KB ok, correct split
8 Correct 131 ms 10756 KB ok, correct split
9 Correct 78 ms 8440 KB ok, correct split
10 Correct 62 ms 8732 KB ok, correct split
11 Correct 70 ms 8816 KB ok, correct split
12 Correct 65 ms 8724 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB invalid split: #1=1, #2=1, #3=3
2 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=1, #2=2, #3=6
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 Incorrect 4 ms 2680 KB invalid split: #1=0, #2=1, #3=3
5 Halted 0 ms 0 KB -