oj.uz

Submission #429127

# Submission time Handle Problem Language Result Execution time Memory
429127 2021-06-15T17:40:04 Z MOUF_MAHMALAT Split the Attractions (IOI19_split) C++14
22 / 100
 592 ms 1048580 KB 
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll sz[100009],x=-1,y=-1,is,c,n;
vector<ll>ans;
vector<vector<ll> >v;
pair<ll,ll>id[3];
void dfs(ll d,ll pp)
{
    sz[d]=1;
    for(auto z:v[d])
        if(z!=pp)
        {
            dfs(z,d);
            sz[d]+=sz[z];
        }
    if(x>-1)
        return;
    for(auto z:v[d])
        if(z!=pp)
        {
            if(sz[z]>=id[0].first&&n-sz[z]>=id[1].first)
            {
                x=z,y=d;
                return;
            }
            if(sz[z]>=id[1].first&&n-sz[z]>=id[0].first)
            {
                x=z,y=d,is=1;
                return;
            }
        }
}
void color(ll d,ll p,ll op)
{
    if(c)
        c--,ans[d]=op;
    else
        ans[d]=id[2].second;
    for(auto z:v[d])
        if(z!=p)
            color(z,d,op);
}
vector<int> find_split(int N, int a, int b, int cc, vector<int> p, vector<int> q)
{
    n=N;
    v.resize(n);
    ans.resize(n);
    id[0]= {a,1};
    id[1]= {b,2};
    id[2]= {cc,3};
    sort(id,id+3);
    for(ll i=0; i<p.size(); i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }
    dfs(0,-1);
    if(x==-1)
        return ans;
    if(is)
    {
        c=id[1].first;
        color(x,y,id[1].second);
        c=id[0].first;
        color(y,x,id[0].second);
    }
    else
    {
        c=id[0].first;
        color(x,y,id[0].second);
        c=id[1].first;
        color(y,x,id[1].second);
    }
    return ans;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:54:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(ll i=0; i<p.size(); i++)
      |                 ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB ok, correct split
2 Runtime error 532 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB ok, correct split
2 Runtime error 527 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB ok, correct split
2 Correct 96 ms 9780 KB ok, correct split
3 Correct 26 ms 4000 KB ok, correct split
4 Correct 1 ms 204 KB ok, correct split
5 Correct 104 ms 12272 KB ok, correct split
6 Correct 83 ms 12008 KB ok, correct split
7 Correct 92 ms 11824 KB ok, correct split
8 Correct 160 ms 13112 KB ok, correct split
9 Correct 105 ms 11556 KB ok, correct split
10 Correct 25 ms 3404 KB ok, no valid answer
11 Correct 30 ms 4960 KB ok, no valid answer
12 Correct 66 ms 9920 KB ok, no valid answer
13 Correct 76 ms 9764 KB ok, no valid answer
14 Correct 75 ms 9944 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 592 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB ok, correct split
2 Runtime error 532 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -