oj.uz

Submission #200011

# Submission time Handle Problem Language Result Execution time Memory
200011 2020-02-04T20:29:58 Z medk Split the Attractions (IOI19_split) C++14
11 / 100
 664 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],b[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);
    }
    sz[u]=n-sz[par];
    sz[par]=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 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 Runtime error 664 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 7 ms 3064 KB ok, correct split
4 Correct 95 ms 9712 KB ok, correct split
5 Correct 78 ms 8688 KB ok, correct split
6 Correct 70 ms 8560 KB ok, correct split
7 Correct 87 ms 11760 KB ok, correct split
8 Correct 126 ms 10992 KB ok, correct split
9 Correct 81 ms 8688 KB ok, correct split
10 Correct 66 ms 9076 KB ok, correct split
11 Correct 60 ms 9076 KB ok, correct split
12 Correct 62 ms 9072 KB ok, correct split

Subtask #3
0 / 22.0

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

Subtask #4
0 / 24.0

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