oj.uz

Submission #153126

# Submission time Handle Problem Language Result Execution time Memory
153126 2019-09-12T14:18:27 Z errorgorn Split the Attractions (IOI19_split) C++14
11 / 100
 132 ms 10548 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][0]];
        }
        while (b--){
            res[pos]=2;
            if (res[al[pos][0]]==0) pos=res[al[pos][1]];
            else pos=res[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 2684 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 2652 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 103 ms 9256 KB ok, correct split
5 Correct 82 ms 8292 KB ok, correct split
6 Correct 85 ms 8184 KB ok, correct split
7 Correct 83 ms 9636 KB ok, correct split
8 Correct 132 ms 10548 KB ok, correct split
9 Correct 84 ms 8184 KB ok, correct split
10 Correct 65 ms 8564 KB ok, correct split
11 Correct 66 ms 8540 KB ok, correct split
12 Correct 72 ms 8560 KB ok, correct split

Subtask #3
0 / 22.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 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 -