oj.uz

답안 #686576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
686576 2023-01-25T13:59:38 Z urosk Split the Attractions (IOI19_split) C++14
18 / 100
 81 ms 15004 KB 
#include "split.h"
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define here cerr<<"============================================\n"
#define ll long long
#define llinf 1000000000000LL
#define sz(a) (ll)(a.size())
#define pb push_back
#define all(a) a.begin(),a.end()
#define popb pop_back
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}

using namespace std;
#define maxn 100005
ll n,m;
vector<ll> g[maxn];
ll x,y,z;
ll col[maxn];
ll siz[maxn],sizmx[maxn],par[maxn];
void dfs1(ll u){
    if(!y) return;
    col[u] = 2;
    y--;
    for(ll s : g[u]) if(!col[s]) dfs1(s);
}
void dfs2(ll u){
    if(x) col[u] = 1,x--;
    else if(y) col[u] = 2,y--;
    else col[u] = 3,z--;
    for(ll s : g[u]) if(!col[s]) dfs2(s);
}
ll nod = -1; bool f;
ll dfssiz(ll u,ll p){
    siz[u] = 1;
    par[u] = p;
    for(ll s : g[u]){
        if(s!=p){
            dfssiz(s,u);
            siz[u]+=siz[s];
            sizmx[u] = max(sizmx[s],sizmx[u]);
        }
    }
    if(nod==-1){
        if(siz[u]>=x&&n-siz[u]>=y){
            nod = u; f = 1;
        }else if(siz[u]>=y&&n-siz[u]>=x){
            nod = u; f = 0;
        }
    }
    return siz[u];
}
void dfscol(ll u,ll w){
    if(!col[u]){
        if((f==1)&&(x>0)){
            col[u] = 1;
            x--;
        }
        else if((f==0)&&(y>0)){
            col[u] = 2; y--;
        }
        else col[u] = 3;
    }
    for(ll s : g[u]){
        if(s==w) continue;
        if(col[s]) continue;
        dfscol(s,w);
    }
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
    n = N;
    m = sz(p);
    x = A,y = B,z = C;
    for(ll i = 0;i<m;i++){
        ll x = p[i],y = q[i];
        x++; y++;
        g[x].pb(y);
        g[y].pb(x);
    }
    ll mxdeg = 0,mndeg = llinf;
    for(ll i = 1;i<=n;i++) mxdeg = max(mxdeg,sz(g[i]));
    for(ll i = 1;i<=n;i++) mndeg = min(mndeg,sz(g[i]));
    if(mxdeg<=2){
        ll poc = 1;
        if(mndeg==1){
            for(ll i = 1;i<=n;i++) if(sz(g[i])==1) poc = i;
        }
        dfs2(poc);
        vector<int> ans(n);
        for(ll i = 1;i<=n;i++) ans[i-1] = col[i];
        return ans;
    }
    if(x==1){
        dfs1(1);
        for(ll i = 1;i<=n;i++){
            if(col[i]) continue;
            if(x){
                col[i] = 1;
                x--;
            }else col[i] = 3;
        }
        vector<int> ans(n);
        for(ll i = 1;i<=n;i++) ans[i-1] = col[i];
        return ans;
    }
    if(m==n-1){
        vector<ll> w = {A,B,C}; sort(all(w)); x = w[0],y = w[1],z = w[2];
        dfssiz(1,1);
        vector<int> ans(n);
        if(nod==-1) return ans;
        for(ll i = 1;i<=n;i++) col[i] = 0;
        dfscol(nod,par[nod]);
        f^=1;
        dfscol(nod,0);
        vector<ll> cur(4);
        for(ll i = 1;i<=n;i++) if(!col[i]) col[i] = 3;
        for(ll i = 1;i<=n;i++) cur[col[i]]++;
        for(ll i = 1;i<=n;i++) ans[i-1] = col[i];
        return ans;
    }
	return {};
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB ok, correct split
2 Correct 1 ms 2644 KB ok, correct split
3 Correct 2 ms 2644 KB ok, correct split
4 Correct 2 ms 2660 KB ok, correct split
5 Correct 2 ms 2652 KB ok, correct split
6 Correct 2 ms 2644 KB ok, correct split
7 Correct 57 ms 12760 KB ok, correct split
8 Correct 72 ms 12752 KB ok, correct split
9 Correct 54 ms 12748 KB ok, correct split
10 Correct 55 ms 12768 KB ok, correct split
11 Correct 71 ms 12720 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB ok, correct split
2 Correct 1 ms 2644 KB ok, correct split
3 Correct 1 ms 2652 KB ok, correct split
4 Correct 67 ms 12728 KB ok, correct split
5 Correct 59 ms 10224 KB ok, correct split
6 Correct 68 ms 12764 KB ok, correct split
7 Correct 68 ms 12776 KB ok, correct split
8 Correct 81 ms 15004 KB ok, correct split
9 Correct 57 ms 9676 KB ok, correct split
10 Correct 46 ms 10032 KB ok, correct split
11 Correct 44 ms 10060 KB ok, correct split
12 Correct 41 ms 10380 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB invalid split: #1=1, #2=2, #3=2
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2644 KB WA in grader: Invalid length of the result.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB ok, correct split
2 Correct 1 ms 2644 KB ok, correct split
3 Correct 2 ms 2644 KB ok, correct split
4 Correct 2 ms 2660 KB ok, correct split
5 Correct 2 ms 2652 KB ok, correct split
6 Correct 2 ms 2644 KB ok, correct split
7 Correct 57 ms 12760 KB ok, correct split
8 Correct 72 ms 12752 KB ok, correct split
9 Correct 54 ms 12748 KB ok, correct split
10 Correct 55 ms 12768 KB ok, correct split
11 Correct 71 ms 12720 KB ok, correct split
12 Correct 1 ms 2644 KB ok, correct split
13 Correct 1 ms 2644 KB ok, correct split
14 Correct 1 ms 2652 KB ok, correct split
15 Correct 67 ms 12728 KB ok, correct split
16 Correct 59 ms 10224 KB ok, correct split
17 Correct 68 ms 12764 KB ok, correct split
18 Correct 68 ms 12776 KB ok, correct split
19 Correct 81 ms 15004 KB ok, correct split
20 Correct 57 ms 9676 KB ok, correct split
21 Correct 46 ms 10032 KB ok, correct split
22 Correct 44 ms 10060 KB ok, correct split
23 Correct 41 ms 10380 KB ok, correct split
24 Incorrect 2 ms 2644 KB invalid split: #1=1, #2=2, #3=2
25 Halted 0 ms 0 KB -