Submission #284808

#	Time	Username	Problem	Language	Result	Execution time	Memory
284808		tmwilliamlin168	Split the Attractions (IOI19_split)	C++14	0 / 100	166 ms	27536 KiB

split

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

#define ar array

const int mxN=1e5;
ar<int, 2> ps[3];
vector<int> ans, adj1[mxN], adj2[2*mxN], st, adj3[mxN], adj4[mxN];
int n, tin[mxN], low[mxN], dt=1, bccI, s[2*mxN], nxt[mxN][2], si[mxN], pa[mxN];
bool cb[mxN];

void dfs1(int u=0, int p=-1) {
//	cout << "d1 " << u << endl;
	tin[u]=low[u]=dt++;
	st.push_back(u);
	for(int v : adj1[u]) {
		if(!tin[v]) {
			int sts=st.size();
			dfs1(v, u);
			low[u]=min(low[v], low[u]);
			if(low[v]>=tin[u]) {
				while(st.size()>sts) {
//					cout << n+bccI << " " << st.back() << endl;
					adj2[n+bccI].push_back(st.back());
					st.pop_back();
				}
//				cout << n+bccI << " " << u << endl;
				adj2[n+bccI].push_back(u);
				adj2[u].push_back(n+bccI++);
			}
		} else if(v^p)
			low[u]=min(tin[v], low[u]);
	}
}

void dfs2(int u=0, int p=-1) {
//	cout << "D2 " << u << endl;
	s[u]=u<n;
	for(int v : adj2[u]) {
		if(v==p)
			continue;
		dfs2(v, u);
		s[u]+=s[v];
	}
}

void dfs4(int u, int p=-1) {
	tin[u]=dt++;
	pa[u]=p;
	for(int v : adj3[u]) {
		if(!tin[v])
			dfs4(v, u);
		else if(tin[v]>tin[u])
			adj4[u].push_back(v);
	}
}

void dfs5(int u) {
	tin[u]=0;
	for(int v : adj4[u]) {
		for(int c=u, d=si[u]>0; !si[v]; v=pa[v], c=nxt[c][d]) {
			si[v]=-si[u];
			nxt[v][d^1]=c;
			nxt[v][d]=nxt[c][d];
			nxt[c][d]=v;
			if(~nxt[v][d])
				nxt[nxt[v][d]][d^1]=v;
		}
	}
	for(int v : adj3[u])
		if(tin[v])
			dfs5(v);
}

void dfs6(int u, int c, int &l) {
	ans[u]=c;
	--l;
	for(int v : adj1[u])
		if(!cb[v]&&l)
			dfs6(v, c, l);
}

void as(vector<int> a, vector<int> b) {
	if(ans[0])
		return;
	fill(ans.begin(), ans.end(), ps[2][1]);
	int la=ps[0][0], lb=ps[1][0];
	for(int c : a)
		dfs6(c, ps[0][1], la);
	for(int c : b)
		dfs6(c, ps[1][1], lb);
}

void dfs3(int u=0, int p=-1) {
//	cout << "d3 " << u << endl;
	if(u>=n) {
		ar<int, 2> mx{};
		for(int v : adj2[u]) {
			cb[v]=1;
			mx=max(ar<int, 2>{s[v], v}, mx);
		}
//		cout << mx[0] << endl;
		if(mx[0]>=ps[1][0]) {
			if(n-mx[0]>=ps[0][0]) {
				vector<int> a=adj2[u];
				a.erase(find(a.begin(), a.end(), mx[1]));
				as(a, {mx[1]});
			}
		} else if(mx[0]>=ps[0][0]) {
			if(n-mx[0]>=ps[1][0]) {
				vector<int> b=adj2[u];
				b.erase(find(b.begin(), b.end(), mx[1]));
				as({mx[1]}, b);
			}
		} else {
			for(int v : adj2[u])
				for(int w : adj1[v])
					if(cb[w])
						adj3[v].push_back(w);
			int cs=0, cu=adj2[u][0];
			dfs4(cu);
			nxt[cu][0]=nxt[cu][1]=-1;
			si[cu]=1;
			dfs5(cu);
			vector<int> a, b;
			while(cs<ps[0][0]) {
				cs+=s[cu];
				a.push_back(cu);
				cu=nxt[cu][1];
			}
			while(~cu) {
				b.push_back(cu);
				cu=nxt[cu][1];
			}
			as(a, b);
		}
		for(int v : adj2[u]) {
			cb[v]=0;
			adj3[v].clear();
			adj4[v].clear();
			si[v]=0;
		}
	}
	for(int v : adj2[u]) {
		if(v==p)
			continue;
		s[u]=n-s[v];
		dfs3(v, u);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	::n=n;
	ps[0]={a, 1};
	ps[1]={b, 2};
	ps[2]={c, 3};
	sort(ps, ps+3);
	for(int i=0; i<p.size(); ++i) {
		adj1[p[i]].push_back(q[i]);
		adj1[q[i]].push_back(p[i]);
	}
	ans=vector<int>(n);
	dfs1();
	dfs2();
	memset(tin, 0, 4*n);
	dfs3();
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'void dfs1(int, int)':
split.cpp:23:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     while(st.size()>sts) {
      |           ~~~~~~~~~^~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:159:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |  for(int i=0; i<p.size(); ++i) {
      |               ~^~~~~~~~~

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