제출 #523166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523166		qwerasdfzxcl	Split the Attractions (IOI19_split)	C++14	0 / 100	2086 ms	12132 KiB

split

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

using namespace std;
typedef long long ll;
struct DSU{
    int path[100100];
    void init(int n){for (int i=0;i<n;i++) path[i] = i;}
    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;
        return 1;
    }
}dsu;
int n, a, b, c, sz[100100], par[100100], idx[5];

void dfs(int s, int &cnt, int no, const vector<vector<int>> &adj, int num, vector<int> &ret){
    if (!cnt) return;
    --cnt;
    ret[s] = num;
    if (no==-1) sz[s] = 1;

    for (auto &v:adj[s]) if (v!=no && ret[v]!=num){
        if (no==-1) par[v] = s;
        dfs(v, cnt, no, adj, num, ret);
        if (no==-1) sz[s] += sz[v];
    }
}

vector<int> solve_tree(const vector<vector<int>> &adj){
    vector<int> ret(n);
    int N = n;
    dfs(0, N, -1, adj, idx[3], ret);
    for (int i=1;i<n;i++){
        int x = sz[i], y = n - sz[i];
        if (a<=x && b<=y){
            dfs(i, a, par[i], adj, idx[1], ret);
            dfs(par[i], b, i, adj, idx[2], ret);
            return ret;
        }
        if (a<=y && b<=x){
            dfs(par[i], a, i, adj, idx[1], ret);
            dfs(i, b, par[i], adj, idx[2], ret);
            return ret;
        }
    }
    fill(ret.begin(), ret.end(), 0);
    return ret;
}

int dist[100100], bp[100100], de = -1, dval = -1;
void bfs(int s, const vector<vector<int>> &adj){
    bp[s] = -1;
    fill(dist, dist+n, 1e9);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while(!q.empty()){
        int cur = q.front(); q.pop();
        for (auto &v:adj[cur]) if (dist[v]==1e9){
            dist[v] = dist[cur] + 1;
            bp[v] = cur;
            q.push(v);
        }
    }

    int mx = *max_element(dist, dist+n);
    if (dval<mx) de = s, dval = mx;
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	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<vector<int>> adj0(N, vector<int>());
	for (int i=0;i<(int)p.size();i++){
        adj0[p[i]].push_back(q[i]);
        adj0[q[i]].push_back(p[i]);
	}

	vector<vector<int>> adj(n);
	dsu.init(n);
	for (int i=0;i<n;i++) bfs(i, adj0);

	bfs(de, adj0);
	int de2 = max_element(dist, dist+n) - dist;
	while(bp[de2]!=-1){
        adj[de2].push_back(bp[de2]);
        adj[bp[de2]].push_back(de2);
        dsu.merge(de2, bp[de2]);

        de2 = bp[de2];
	}

	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]);
	}

	return solve_tree(adj);
}

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