Submission #1055655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055655		HD1	Split the Attractions (IOI19_split)	C++17	0 / 100	427 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define sz(s) int(s.size())
#define pb push_back
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
//typedef pair<int,int> ii;
const ll MAX=1e6+10;
using namespace std;
vector<int> gfo[MAX];
vector<pair<ll,ll>> ord;
ll tam[MAX], m[MAX];
ll a, b, c, n;
bool xd=false;
void dfstams(ll u, ll f){
    for(auto v:gfo[u]){
        if(v!=f){
            dfstams(v,u);
            tam[u]+=tam[v];
        }
    }
    tam[u]++;
    return;
}
ll cont;
void dfs(ll u, ll f, ll marc){
    if(cont==ord[marc].ff)return;
    m[u]=ord[marc].ss;
    cont++;
    if(cont==ord[marc].ff)return;
    for(auto v:gfo[u]){
        if(v!=f){
            dfs(v,u,marc);
        }
    }
    return;
}
bool lock(ll u, ll v){//arista
    ll q=n-tam[u];///v
    ll p=tam[u];/// u
    cont=0;
    if(p>=ord[0].ff && q>=ord[1].ff){
        dfs(u, v, 0);
        cont=0;
        dfs(v, u, 1);
        xd=true;
        return true;
    }
    return false;
}
void clean(){
    xd=false;
    ord.clear();
    for(int i=0; i<n; i++){
        gfo[i].clear();
        tam[i]=0;
        m[i]=0;
    }
    return;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> u, vector<int> v) {
	a=A;
	b=B;
	c=C;
	n=N;
    ord.pb({a,1});
    ord.pb({b,2});
    ord.pb({c,3});
    sort(all(ord));
	vector<int> res;
	for(int i=0; i<sz(u); i++){
		gfo[u[i]].pb(v[i]);
		gfo[v[i]].pb(u[i]);
	}
    dfstams(0, 0);
    for(ll i=0; i<n; i++){
        for(ll v:gfo[i]){
            if(lock(i,v))break;
        }
        if(xd)break;
    }
    for(int i=0; i<n; i++){
        if(xd && m[i]==0){
            m[i]=ord[2].ss;
        }
    }
    for(int i=0; i<n; i++){
        res.pb(m[i]);
    }
    clean();
    return res;
}
/*
9 8
2 3 4
0 1
0 7
0 2
1 6
1 3
2 5
2 8
2 4
 
8 7
2 3 3
0 1
1 2
1 7
1 3
3 4
4 5
4 6

7 6
4 2 2
 
*/

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36