Submission #620681

#	Time	Username	Problem	Language	Result	Execution time	Memory
620681		TimDee	Split the Attractions (IOI19_split)	C++17	40 / 100	119 ms	16320 KiB

split

#include "split.h"
using namespace std;
using ll=long long;
#include <bits/stdc++.h>

int maxn=1e5;
vector<int> s;
vector<int> vis(maxn,0);
vector<vector<int>> adj(maxn);
int cnt=0, now=1;
int n,a,b,c;

void dfs(int u) {
	if (vis[u]) return;
	vis[u]=1;
	cnt++;
	if (now==1) {
		if (cnt<=a) s[u]=1;
		else {
			cnt=1; now=2;
		}
	}
	if (now==2) {
		if (cnt<=b) s[u]=2;
		else {
			cnt=1; now=3;
		}
	}
	if (now==3) {
		if (cnt<=c) s[u]=3;
		else {
			cnt=1; now=4;
		}
	}

	for (auto v:adj[u]) {
		dfs(v);
	}
}

struct DSU {
 
    vector<int> p;
    vector<int> r;
    vector<int> sz;
    
    DSU(int n) {
        p.assign(n,0);
        r.assign(n,0);
        sz.assign(n,1);
        for (int i=0; i<n; ++i) p[i]=i;
    }

    int get(int i) {
           
        return p[i]==i ? i : get(p[i]);
        
    }

    int getsz(int i) {
		i=get(i);
		return sz[i];
	}
    
    void uni(int a, int b) {
        
        a=get(a);
        b=get(b);
        if (a==b) return;
        
        if (r[a]==r[b]) r[a]++;
        
        if (r[a]>r[b]) {
            p[b]=a;
            sz[a]+=sz[b];
        } else {
            p[a]=b;
            sz[b]+=sz[a];
        }
        
    }
    
};

vector<int> par(1e5,-1);
void _dfs(vector<int>&c, int v) {
	if (vis[v]) return;
	vis[v]=1;
	for (auto u:adj[v]) {
		if (!vis[u]) par[u]=v;
		if (u==par[v]) continue;
		_dfs(c,u);
		c[v]+=c[u];
	}
	//cout<<v<<' '<<c[v]<<'\n';
}

int findcentroid(vector<int>&c, int v) {
	for (auto u:adj[v]) {
		if (u==par[v]) continue;
		if (c[u]>n/2) return findcentroid(c,u);
	}
	return v;
}

vector<int> _p3() {
	
	int _b, _a;
	vector<int> tmp={a,b,c}; sort(tmp.begin(), tmp.end());
	_b=tmp[1]; _a=tmp[0];
	s.assign(n,0);
	vector<int> ch(n,1);
	_dfs(ch,0);
	int cent=findcentroid(ch,0);
	
	ch.assign(n,1);
	vis.assign(n,0);
	par.assign(n,-1);
	_dfs(ch,cent);

	int ind=adj[cent][0];
	for (auto v:adj[cent]) if (ch[ind]<ch[v]) ind=v;
	int mx=ch[ind];
	if (mx<_a) return s;
	int A,B,C;
	if (a<b) {
		if (a<c) A=1;
		else A=3;
		if (b<c) { B=2; C=(A+2)%4; }
		else { B=(A+2)%4; C=2; }
	} else {
		if (b<c) A=2;
		else A=3;
		if (a<c) { B=1; C=A+1-2*(A%2); }
		else { B=A+1-2*(A%2); C=1; }
	}
	vis.assign(n,0);
	s.assign(n,C);
	int cnt=0;
	queue<int> q; q.push(ind); vis[cent]=1; vis[ind]=1;
	while (cnt<_a) {
		int u=q.front(); q.pop();
		s[u]=A;
		for (auto v:adj[u]) {
			if (!vis[v]) {
				vis[v]=1;
				q.push(v);
			}
		}
		++cnt;
	}
	while (q.size()) q.pop();
	q.push(cent); cnt=0;
	while (cnt<_b) {
		int u=q.front(); q.pop();
		s[u]=B;
		for (auto v:adj[u]) {
			if (!vis[v]) {
				vis[v]=1;
				q.push(v);
			}
		}
		++cnt;
	}

	return s;

}

vector<int> find_split(int N, int A, int B, int C, vector<int>p, vector<int> q) {
	int m=p.size();
	n=N, a=A, b=B, c=C;
	s.assign(n,0);
	for (int i=0; i<m; ++i) {
		int u=p[i], v=q[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	if (m==n-1) return _p3();
	int foo=1, start=0;
	for (int i=0; i<n; ++i) {
		foo&=adj[i].size()<=2;
		if (adj[i].size()==1) start=i;
	}
	if (foo) {
		dfs(start);
		return s;
	}
	if (a==1) {
		s.assign(n,3);
		queue<int> q; q.push(0); vis[0]=1;
		int cnt=0;
		while (cnt<b) {
			int u=q.front(); q.pop();
			s[u]=2;
			cnt++;
			for (auto v:adj[u]) {
				if (!vis[v]) {
					vis[v]=1;
					q.push(v);
				}
			}
		}
		for (int i=0; i<n; ++i) if (s[i]==3) {s[i]=1; break;}
		return s;
	}
	return vector<int>(n,0);
}

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