Submission #525853

#	Time	Username	Problem	Language	Result	Execution time	Memory
525853		qwerasdfzxcl	Split the Attractions (IOI19_split)	C++14	100 / 100	120 ms	15696 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct DSU{
    int path[100100], sz[100100];
    void init(int n){for (int i=0;i<n;i++) path[i] = i, sz[i] = 1;}
    int find(int s){
        if (s==path[s]) return s;
        return path[s] = find(path[s]);
    }
    bool merge(int s, int v){
        s = find(s), v = find(v);
        if (s==v) return 0;
        path[s] = v;
        sz[v] += sz[s];
        return 1;
    }
    int getsz(int s){return sz[find(s)];}
}dsu;
int n, a, b, c, sz[100100], sidx[100100], idx[5];
vector<int> adj[100100], ret;

int getsz(int s, int pa = -1){
    sz[s] = 1;
    for (auto &v:adj[s]) if (v!=pa) sz[s] += getsz(v, s);
    return sz[s];
}

int cent;
int getcent(int s, int pa = -1){
    for (auto &v:adj[s]) if (v!=pa && sz[v]*2>=n) return getcent(v, s);
    return s;
}

void dfs(int s, int val, int pa){
    sidx[s] = val;
    for (auto &v:adj[s]) if (v!=pa) dfs(v, val, s);
}

int cnt0 = 0;
void dfs0(int s, int pa = -1){
    if (cnt0>=a) return;
    ++cnt0;
    ret[s] = idx[1];
    for (auto &v:adj[s]) if (v!=pa && v!=cent) dfs0(v, s);
}

int cnt1 = 0;
void dfs1(int s, int x, int pa = -1){
    if (cnt1>=b) return;
    ret[s] = idx[2];
    ++cnt1;
    for (auto &v:adj[s]) if (v!=pa && !ret[v]) dfs1(v, x, s);
}

void solve_tree(){
    getsz(0);
    cent = getcent(0);
    getsz(cent);

    int cnt = 1;
    dsu.init(n);
    for (auto &v:adj[cent]) dfs(v, cnt++, cent);
    for (auto &v:adj[cent]) dsu.sz[sidx[v]] = sz[v];

    for (auto &v:adj[cent]) if (sz[v]>=a){
        dfs0(v);
        dfs1(cent, sidx[v]);
        for (auto &x:ret) if (!x) x = idx[3];
        return;
    }
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
    ret.resize(N);
	n = N;
	vector<pair<int, int>> tmp;
	tmp.emplace_back(A, 1);
	tmp.emplace_back(B, 2);
	tmp.emplace_back(C, 3);

	sort(tmp.begin(), tmp.end());
	a = tmp[0].first, b = tmp[1].first, c = tmp[2].first;
	idx[1] = tmp[0].second, idx[2] = tmp[1].second, idx[3] = tmp[2].second;

	vector<pair<int, int>> E;
	dsu.init(n);

	for (int i=0;i<(int)p.size();i++) {
        if (dsu.merge(p[i], q[i])){
            adj[p[i]].push_back(q[i]);
            adj[q[i]].push_back(p[i]);
        }
        else E.emplace_back(p[i], q[i]);
	}

	solve_tree();
	if (ret[0]) return ret;


	int v = -1;
	for (auto &p:E) if (p.first!=cent && p.second!=cent){
        if (dsu.merge(sidx[p.first], sidx[p.second])){
            adj[p.first].push_back(p.second);
            adj[p.second].push_back(p.first);
        }

        if (dsu.getsz(sidx[p.first])>=a){
            dfs0(p.first);
            assert(cnt0==a);
            v = p.first;
            break;
        }
	}
	if (v==-1) return ret;

	dfs1(cent, sidx[v]);
	if (cnt1!=b) exit(1);

	for (auto &x:ret) if (!x) x = idx[3];
	return ret;
}

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