oj.uz

Submission #153127

# Submission time Handle Problem Language Result Execution time Memory
153127 2019-09-12T14:19:02 Z errorgorn Split the Attractions (IOI19_split) C++14
11 / 100
 129 ms 10472 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][1];
            else pos=al[pos][0];
        }
        while (b--){
            res[pos]=2;
            if (res[al[pos][0]]==0) pos=al[pos][1];
            else pos=al[pos][0];
        }
        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=1, #2=1, #3=2
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 4 ms 2680 KB ok, correct split
4 Correct 99 ms 9340 KB ok, correct split
5 Correct 78 ms 8184 KB ok, correct split
6 Correct 74 ms 8128 KB ok, correct split
7 Correct 88 ms 9632 KB ok, correct split
8 Correct 129 ms 10472 KB ok, correct split
9 Correct 82 ms 8188 KB ok, correct split
10 Correct 67 ms 8560 KB ok, correct split
11 Correct 66 ms 8560 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 Incorrect 4 ms 2680 KB 2 components are not connected
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=0, #2=2, #3=7
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=1, #2=1, #3=2
5 Halted 0 ms 0 KB -