Submission #1055635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055635		HD1	Split the Attractions (IOI19_split)	C++14	0 / 100	437 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=1e5+5;
using namespace std;
vector<int> gfo[MAX];
vector<pair<ll,ll>> ord;
int tam[MAX], m[MAX];
int a, b, c, n;
bool xd=false;
void dfstams(int u, int f){
    for(auto v:gfo[u]){
        if(v!=f){
            dfstams(v,u);
            tam[u]+=tam[v];
        }
    }
    tam[u]++;
    return;
}
int cont;
void dfs(int u, int f, int 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);
        }
    }
}
bool lock(int u, int v){//arista
    if(tam[u]>tam[v])swap(u,v);// u siempre el de abajo
    ll q=n-tam[u];
    ll p=tam[u];
    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;
}
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(int i=0; i<n; i++){
        for(auto 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]=3;
        }
    }
    for(int i=0; i<n; i++){
        res.pb(m[i]);
    }
    return res;
}
/*
8 7
2 3 3
0 1
1 6
6 7
7 5
5 4
4 3
3 2
0 2
 
8 7
2 3 3
0 1
1 2
1 7
1 3
3 4
4 5
4 6
 
*/

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