Submission #131486

#	Time	Username	Problem	Language	Result	Execution time	Memory
131486		tmwilliamlin168	Simurgh (IOI17_simurgh)	C++14	0 / 100	2 ms	376 KiB

simurgh

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

const int mxN=500, mxM=mxN*(mxN-1)/2;
int n, tin[mxN], low[mxN], dt=1, b[mxM], bs, st[mxM], sth, t[mxN], p[mxN];
vector<int> eu, ev, adj[mxN], ans;
bool c[mxN];

//debug stuff
void pv(string s, vector<int> v) {
	cout << s << endl;
	for(int i : v)
		cout << i << " ";
	cout << endl;
}

void dfs1(int u=0, int p=-1) {
	tin[u]=low[u]=dt++;
	for(int e : adj[u]) {
		int v=eu[e]^ev[e]^u;
		if(!tin[v]) {
			st[sth++]=e;
			dfs1(v, u);
			low[u]=min(low[v], low[u]);
			if(low[u]>=tin[u]) {
				do {
					b[st[--sth]]=bs;
				} while(st[sth]^e);
				++bs;
			}
		} else if(tin[v]<tin[u]) {
			st[sth++]=e;
			low[u]=min(tin[v], low[u]);
		}
	}
}

int find(int x) {
	return x^p[x]?p[x]=find(p[x]):x;
}

bool join(int x, int y) {
	if((x=find(x))==(y=find(y)))
		return 0;
	p[x]=y;
	return 1;
}

vector<int> fst(vector<int> w) {
	vector<int> r;
	iota(p, p+n, 0);
	for(int i=0; i<eu.size(); ++i) {
		//cout << "fst " << i << endl;
		if(w[eu[i]]&&w[ev[i]]&&join(eu[i], ev[i]))
			r.push_back(i);
	}
	return r;
}

void dc(vector<int> &a, vector<int> &b, vector<int> &c, int l, int r, int s1, int s2) {
	if(s2==s1)
		return;
	if(l==r) {
		c.push_back(b[l]);
		return;
	}
	int m=(l+r)/2;
	vector<int> d=a;
	for(int i=l; i<=r; ++i)
		d[i]=b[i];
	int sl=count_common_roads(d);
	dc(a, b, c, l, m, s1, sl);
	dc(a, b, c, m+1, r, s1, s2-sl+s1);
}

void dfs2(int u=0) {
	//cout << "d2 " << u << endl;
	vector<int> v1, v2, r;
	for(int e : adj[u]) {
		int v=eu[e]^ev[e]^u;
		if(c[v])
			continue;
		if(t[v]<0) {
			v2.push_back(e);
			t[v]=e;
		} else
			v1.push_back(e);
	}
	if(v1.size()) {
		//pv("pv1", v1);
		vector<int> w(n, 1);
		for(int e : v1)
			w[eu[e]^ev[e]^u]=0;
		vector<int> s1=fst(w), s2=s1;
		s2.insert(s2.begin(), v1.begin(), v1.end());
		//pv("s1", s1);
		//pv("s2", s2);
		for(int i=0; i<v1.size(); ++i)
			s1.insert(s1.begin()+i, t[eu[v1[i]]^ev[v1[i]]^u]);
		dc(s1, v1, r, 0, v1.size()-1, count_common_roads(s1), count_common_roads(s2));
		//pv("r", r);
	}
	if(v2.size()) {
		//pv("pv2", v2);
		vector<int> w(n, 1);
		w[u]=0;
		vector<int> s=fst(w);
		//pv("s1", s);
		for(int e : ans)
			if(join(eu[e], ev[e]))
				s.push_back(e);
		for(int e : r)
			if(join(eu[e], ev[e]))
				s.push_back(e);
		for(int e : adj[u])
			if(join(eu[e], ev[e]))
				s.push_back(e);
		//pv("s2", s);
		int bc=count_common_roads(s);
		//cout << bc << endl;
		sort(v2.begin(), v2.end(), [](const int &i, const int &j) {
			return b[i]<b[j];
		});
		for(int i=0, j=0; i<v2.size(); ) {
			//cout << "hi2 " << i << endl;
			for(; j<v2.size()&&b[v2[j]]==b[v2[i]]; ++j);
			int o;
			for(int e : s)
				if(b[e]==b[v2[i]])
					o=e;
			s.erase(find(s.begin(), s.end(), o));
			//cout << "edge removed " << o << endl;
			vector<int> a;
			int cm=bc;
			for(; i<j; ++i) {
				s.push_back(v2[i]);
				int cc=count_common_roads(s);
				if(cc>cm) {
					cm=cc;
					a=vector<int>();
				}
				if(cc==cm)
					a.push_back(v2[i]);
				s.pop_back();
			}
			//cout << cm << endl;
			//pv("on", a);
			r.insert(r.end(), a.begin(), a.end());
			s.push_back(o);
		}
	}
	for(int e : r) {
		ans.push_back(e);
		c[eu[e]^ev[e]^u]=1;
	}
	for(int e : r)
		dfs2(eu[e]^ev[e]^u);
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	::n=n;
	eu=u;
	ev=v;
	for(int i=0; i<u.size(); ++i) {
		adj[u[i]].push_back(i);
		adj[v[i]].push_back(i);
	}
	dfs1();
	c[0]=1;
	memset(t, -1, 4*n);
	dfs2();
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> fst(std::vector<int>)':
simurgh.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<eu.size(); ++i) {
               ~^~~~~~~~~~
simurgh.cpp: In function 'void dfs2(int)':
simurgh.cpp:99:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v1.size(); ++i)
                ~^~~~~~~~~~
simurgh.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0, j=0; i<v2.size(); ) {
                     ~^~~~~~~~~~
simurgh.cpp:127:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; j<v2.size()&&b[v2[j]]==b[v2[i]]; ++j);
          ~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:165:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<u.size(); ++i) {
               ~^~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30