oj.uz

Submission #200016

# Submission time Handle Problem Language Result Execution time Memory
200016 2020-02-04T20:42:43 Z medk Split the Attractions (IOI19_split) C++14
40 / 100
 689 ms 1048580 KB 
#include <bits/stdc++.h>
#include "split.h"

#define ll long long
#define ld long double
#define pb push_back
#define x first
#define y second

using namespace std;

int n,m;
vector<vector<int>> g(100000);
int a[3];
vector<int> sz(100000),ans;
bool done=0;
int cnt=0;
set<int> st={0,1,2};
bool vis[100000];

void dfs1(int u, int par)
{
    sz[u]=1;
    for(int v:g[u])
    {
        if(v==par) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
    }
}

void dfs3(int u, int par, int val)
{
    vis[u]=1;
    cnt++;
    ans[u]=val;
    for(int v:g[u])
    {
        if(v==par || vis[v]) continue;
        if(cnt>=a[val]) break;
        dfs3(v,u,val);
    }
}

void dfs2(int u, int par)
{
    if(done) return;
    if(par!=-1) sz[par]-=sz[u];
    sz[u]=n;
    int found=-1, which=-1, which2=-1;
    for(int v:g[u])
    {
        if(sz[v]>=a[0])
        {
            if(n-sz[v]>=a[1])
            {
                found=v;
                which=0;
                which2=1;
                break;
            }
            if(n-sz[v]>=a[2])
            {
                found=v;
                which=0;
                which2=2;
                break;
            }
        }
        if(sz[v]>=a[1])
        {
            if(n-sz[v]>=a[2])
            {
                found=v;
                which=1;
                which2=2;
                break;
            }
            if(n-sz[v]>=a[0])
            {
                found=v;
                which=1;
                which2=0;
                break;
            }
        }
        if(sz[v]>=a[2])
        {
            if(n-sz[v]>=a[1])
            {
                found=v;
                which=2;
                which2=1;
                break;
            }
            if(n-sz[v]>=a[0])
            {
                found=v;
                which=2;
                which2=0;
                break;
            }
        }
        if(v!=par) dfs2(v,u);
    }
    if(found>=0)
    {
        done=1;
        st.erase(which);
        st.erase(which2);
        dfs3(found,u,which);
        cnt=0;
        dfs3(u,found,which2);
    }
    if(par!=-1) sz[u]=n-sz[par], sz[par]=n;
    else sz[u]=n;
}

vector<int> find_split(int N, int d, int b, int c, vector<int> p, vector<int> q)
{
    n=N;
    m=p.size();
    a[0]=d, a[1]=b, a[2]=c;
    for(int i=0;i<n;i++) ans.pb(-1);
    for(int i=0;i<m-(a[0]!=1 && n==m);i++)
    {
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
    }
    if(a[0]==1)
    {
        dfs3(0,0,1);
        int to=0;
        for(int i=0;i<n;i++) if(ans[i]==-1){ans[i]=to;if(to==0)to=2;}
        for(int i=0;i<n;i++) ans[i]++;
    }
    else{
    dfs1(0,-1);
    dfs2(0,-1);
    if(done)
        for(int i=0;i<n;i++) if(ans[i]==-1) ans[i]=*st.begin();
    for(int i=0;i<n;i++) ans[i]++;}
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3064 KB ok, correct split
2 Correct 6 ms 3064 KB ok, correct split
3 Correct 6 ms 3064 KB ok, correct split
4 Correct 6 ms 3064 KB ok, correct split
5 Correct 7 ms 3064 KB ok, correct split
6 Correct 7 ms 3064 KB ok, correct split
7 Correct 116 ms 15728 KB ok, correct split
8 Correct 100 ms 13988 KB ok, correct split
9 Correct 106 ms 13400 KB ok, correct split
10 Correct 96 ms 9668 KB ok, correct split
11 Correct 109 ms 14832 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3064 KB ok, correct split
2 Correct 7 ms 3064 KB ok, correct split
3 Correct 7 ms 3064 KB ok, correct split
4 Correct 104 ms 9840 KB ok, correct split
5 Correct 88 ms 8816 KB ok, correct split
6 Correct 76 ms 8560 KB ok, correct split
7 Correct 88 ms 11828 KB ok, correct split
8 Correct 126 ms 10992 KB ok, correct split
9 Correct 84 ms 8688 KB ok, correct split
10 Correct 60 ms 9072 KB ok, correct split
11 Correct 63 ms 9072 KB ok, correct split
12 Correct 77 ms 9048 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3068 KB ok, correct split
2 Correct 92 ms 8816 KB ok, correct split
3 Correct 31 ms 5364 KB ok, correct split
4 Correct 7 ms 3064 KB ok, correct split
5 Correct 107 ms 10736 KB ok, correct split
6 Correct 103 ms 10480 KB ok, correct split
7 Correct 106 ms 11376 KB ok, correct split
8 Correct 111 ms 11632 KB ok, correct split
9 Correct 109 ms 11248 KB ok, correct split
10 Correct 29 ms 4980 KB ok, no valid answer
11 Correct 40 ms 5876 KB ok, no valid answer
12 Correct 76 ms 8816 KB ok, no valid answer
13 Correct 97 ms 8688 KB ok, no valid answer
14 Correct 66 ms 8944 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 689 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3064 KB ok, correct split
2 Correct 6 ms 3064 KB ok, correct split
3 Correct 6 ms 3064 KB ok, correct split
4 Correct 6 ms 3064 KB ok, correct split
5 Correct 7 ms 3064 KB ok, correct split
6 Correct 7 ms 3064 KB ok, correct split
7 Correct 116 ms 15728 KB ok, correct split
8 Correct 100 ms 13988 KB ok, correct split
9 Correct 106 ms 13400 KB ok, correct split
10 Correct 96 ms 9668 KB ok, correct split
11 Correct 109 ms 14832 KB ok, correct split
12 Correct 7 ms 3064 KB ok, correct split
13 Correct 7 ms 3064 KB ok, correct split
14 Correct 7 ms 3064 KB ok, correct split
15 Correct 104 ms 9840 KB ok, correct split
16 Correct 88 ms 8816 KB ok, correct split
17 Correct 76 ms 8560 KB ok, correct split
18 Correct 88 ms 11828 KB ok, correct split
19 Correct 126 ms 10992 KB ok, correct split
20 Correct 84 ms 8688 KB ok, correct split
21 Correct 60 ms 9072 KB ok, correct split
22 Correct 63 ms 9072 KB ok, correct split
23 Correct 77 ms 9048 KB ok, correct split
24 Correct 7 ms 3068 KB ok, correct split
25 Correct 92 ms 8816 KB ok, correct split
26 Correct 31 ms 5364 KB ok, correct split
27 Correct 7 ms 3064 KB ok, correct split
28 Correct 107 ms 10736 KB ok, correct split
29 Correct 103 ms 10480 KB ok, correct split
30 Correct 106 ms 11376 KB ok, correct split
31 Correct 111 ms 11632 KB ok, correct split
32 Correct 109 ms 11248 KB ok, correct split
33 Correct 29 ms 4980 KB ok, no valid answer
34 Correct 40 ms 5876 KB ok, no valid answer
35 Correct 76 ms 8816 KB ok, no valid answer
36 Correct 97 ms 8688 KB ok, no valid answer
37 Correct 66 ms 8944 KB ok, no valid answer
38 Runtime error 689 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Halted 0 ms 0 KB -