oj.uz

답안 #200014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200014 2020-02-04T20:36:59 Z medk Split the Attractions (IOI19_split) C++14
11 / 100
 674 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];
    if(par!=-1) 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

# 결과 실행 시간 메모리 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 674 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

# 결과 실행 시간 메모리 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 Correct 108 ms 9712 KB ok, correct split
5 Correct 76 ms 8688 KB ok, correct split
6 Correct 86 ms 8560 KB ok, correct split
7 Correct 91 ms 11760 KB ok, correct split
8 Correct 133 ms 10976 KB ok, correct split
9 Correct 80 ms 8688 KB ok, correct split
10 Correct 58 ms 9072 KB ok, correct split
11 Correct 61 ms 8944 KB ok, correct split
12 Correct 62 ms 9072 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3064 KB ok, correct split
2 Incorrect 103 ms 8944 KB invalid split: #1=20000, #2=70593, #3=9407
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 645 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

# 결과 실행 시간 메모리 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 674 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -