oj.uz

Submission #200010

# Submission time Handle Problem Language Result Execution time Memory
200010 2020-02-04T20:20:42 Z medk Split the Attractions (IOI19_split) C++14
11 / 100
 1095 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{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 1095 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 8 ms 3192 KB ok, correct split
3 Correct 7 ms 3064 KB ok, correct split
4 Correct 98 ms 9724 KB ok, correct split
5 Correct 75 ms 8816 KB ok, correct split
6 Correct 75 ms 8688 KB ok, correct split
7 Correct 89 ms 11888 KB ok, correct split
8 Correct 123 ms 11120 KB ok, correct split
9 Correct 81 ms 8816 KB ok, correct split
10 Correct 65 ms 9072 KB ok, correct split
11 Correct 59 ms 9200 KB ok, correct split
12 Correct 60 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 652 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 1095 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -