oj.uz

Submission #200013

# Submission time Handle Problem Language Result Execution time Memory
200013 2020-02-04T20:35:53 Z medk Split the Attractions (IOI19_split) C++14
11 / 100
 728 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];
int found=-1, which=-1, which2=-1;

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;
    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;
}

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 3192 KB ok, correct split
2 Correct 7 ms 3064 KB ok, correct split
3 Correct 6 ms 3068 KB ok, correct split
4 Runtime error 728 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 7 ms 3064 KB ok, correct split
2 Correct 7 ms 3064 KB ok, correct split
3 Correct 6 ms 3064 KB ok, correct split
4 Correct 105 ms 9712 KB ok, correct split
5 Correct 76 ms 8688 KB ok, correct split
6 Correct 78 ms 8560 KB ok, correct split
7 Correct 91 ms 11760 KB ok, correct split
8 Correct 135 ms 10992 KB ok, correct split
9 Correct 92 ms 8688 KB ok, correct split
10 Correct 61 ms 9072 KB ok, correct split
11 Correct 59 ms 9104 KB ok, correct split
12 Correct 66 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 695 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 3192 KB ok, correct split
2 Correct 7 ms 3064 KB ok, correct split
3 Correct 6 ms 3068 KB ok, correct split
4 Runtime error 728 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -