oj.uz

Submission #200015

# Submission time Handle Problem Language Result Execution time Memory
200015 2020-02-04T20:41:15 Z medk Split the Attractions (IOI19_split) C++14
33 / 100
 706 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;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{
    if(m==n) g[0].erase(g[0].begin());
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 Runtime error 706 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.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 110 ms 10100 KB ok, correct split
5 Correct 77 ms 9072 KB ok, correct split
6 Correct 81 ms 8816 KB ok, correct split
7 Correct 90 ms 12144 KB ok, correct split
8 Correct 133 ms 11376 KB ok, correct split
9 Correct 91 ms 9072 KB ok, correct split
10 Correct 60 ms 9328 KB ok, correct split
11 Correct 64 ms 9328 KB ok, correct split
12 Correct 69 ms 9328 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3064 KB ok, correct split
2 Correct 96 ms 9072 KB ok, correct split
3 Correct 33 ms 5748 KB ok, correct split
4 Correct 6 ms 3064 KB ok, correct split
5 Correct 113 ms 11888 KB ok, correct split
6 Correct 107 ms 11632 KB ok, correct split
7 Correct 115 ms 12532 KB ok, correct split
8 Correct 125 ms 12784 KB ok, correct split
9 Correct 115 ms 12272 KB ok, correct split
10 Correct 29 ms 5236 KB ok, no valid answer
11 Correct 41 ms 6388 KB ok, no valid answer
12 Correct 90 ms 9968 KB ok, no valid answer
13 Correct 106 ms 9784 KB ok, no valid answer
14 Correct 68 ms 10096 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 668 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 7 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 Runtime error 706 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -