oj.uz

Submission #143908

# Submission time Handle Problem Language Result Execution time Memory
143908 2019-08-15T12:38:38 Z Bodo171 Split the Attractions (IOI19_split) C++14
29 / 100
 146 ms 14456 KB 
#include "split.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int nmax=100005;
vector<int> res;
vector<int> v[nmax];
pair<int,int> C[3];
int viz[nmax],q[nmax],w[nmax],tt[nmax];
int i,n;
void sterge(int A,int B)
{
    for(int it=0;it<2;it++)
    {
        for(int i=0;i<v[A].size();i++)
            if(v[A][i]==B)
        {
            swap(v[A][i],v[A].back());
            v[A].pop_back();
        }
        swap(A,B);
    }
}
void et(int x,int cate,int col)
{
    int p,u;
    for(i=0;i<n;i++)
        viz[i]=0;
    viz[x]=1;
    q[u=1]=x;
    for(p=1;p<=u;p++)
    {
        x=q[p];
        for(int i=0;i<v[x].size();i++)
            if(!viz[v[x][i]])
        {
            q[++u]=v[x][i];
            viz[v[x][i]]=1;
        }
    }
    for(i=1;i<=cate;i++)
        res[q[i]]=col;
}
bool gasit;
void solve(int x)
{
    w[x]=1;
    for(int i=0;i<v[x].size();i++)
        if((!w[v[x][i]]))
    {
        tt[v[x][i]]=x;
        solve(v[x][i]);
        w[x]+=w[v[x][i]];
    }
    if(!gasit)
    {
        if(w[x]>=C[0].first&&n-w[x]>=C[1].first)
        {
            sterge(x,tt[x]);
            et(x,C[0].first,C[0].second);
            et(tt[x],C[1].first,C[1].second);
            gasit=1;
        }
        else
        {
            if(w[x]>=C[1].first&&n-w[x]>=C[0].first)
            {
                sterge(x,tt[x]);
                et(x,C[1].first,C[1].second);
                et(tt[x],C[0].first,C[0].second);
                gasit=1;
            }
        }
    }
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
    n=nn;
    for(i=0;i<p.size();i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }
    res.resize(n);
    for(i=0;i<n;i++)
        res[i]=0;
    pair<int,int> v[3];
    C[0]={a,1};
    C[1]={b,2};
    C[2]={c,3};
    sort(C,C+3);
    solve(0);
    if(gasit)
    {
        int oth=(C[0].second^C[1].second);
        for(i=0; i<n; i++)
            if(!res[i])
                res[i]=oth;
    }
	return res;
}

Compilation message

split.cpp: In function 'void sterge(int, int)':
split.cpp:15:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[A].size();i++)
                     ~^~~~~~~~~~~~
split.cpp: In function 'void et(int, int, int)':
split.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[x].size();i++)
                     ~^~~~~~~~~~~~
split.cpp: In function 'void solve(int)':
split.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:78:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<p.size();i++)
             ~^~~~~~~~~
split.cpp:86:19: warning: unused variable 'v' [-Wunused-variable]
     pair<int,int> v[3];
                   ^

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 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 109 ms 14072 KB ok, correct split
8 Correct 115 ms 12792 KB ok, correct split
9 Correct 109 ms 12412 KB ok, correct split
10 Correct 118 ms 14452 KB ok, correct split
11 Correct 116 ms 14328 KB ok, correct split

Subtask #2
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 121 ms 13020 KB ok, correct split
5 Correct 95 ms 9860 KB ok, correct split
6 Correct 112 ms 14456 KB ok, correct split
7 Correct 101 ms 12664 KB ok, correct split
8 Incorrect 146 ms 12152 KB invalid split: #1=0, #2=33333, #3=66667
9 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 92 ms 9848 KB ok, correct split
3 Correct 33 ms 5496 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 102 ms 11064 KB ok, correct split
6 Correct 116 ms 10968 KB ok, correct split
7 Correct 111 ms 10996 KB ok, correct split
8 Correct 95 ms 11640 KB ok, correct split
9 Correct 108 ms 10872 KB ok, correct split
10 Correct 27 ms 4856 KB ok, no valid answer
11 Correct 40 ms 5880 KB ok, no valid answer
12 Correct 86 ms 9264 KB ok, no valid answer
13 Correct 89 ms 9080 KB ok, no valid answer
14 Correct 68 ms 9456 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, no valid answer
3 Correct 5 ms 2680 KB ok, correct split
4 Incorrect 4 ms 2680 KB invalid split: #1=4, #2=2, #3=5
5 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 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 109 ms 14072 KB ok, correct split
8 Correct 115 ms 12792 KB ok, correct split
9 Correct 109 ms 12412 KB ok, correct split
10 Correct 118 ms 14452 KB ok, correct split
11 Correct 116 ms 14328 KB ok, correct split
12 Correct 4 ms 2680 KB ok, correct split
13 Correct 4 ms 2680 KB ok, correct split
14 Correct 4 ms 2680 KB ok, correct split
15 Correct 121 ms 13020 KB ok, correct split
16 Correct 95 ms 9860 KB ok, correct split
17 Correct 112 ms 14456 KB ok, correct split
18 Correct 101 ms 12664 KB ok, correct split
19 Incorrect 146 ms 12152 KB invalid split: #1=0, #2=33333, #3=66667
20 Halted 0 ms 0 KB -