Submission #135033

#	Time	Username	Problem	Language	Result	Execution time	Memory
135033		tmwilliamlin168	Simurgh (IOI17_simurgh)	C++14	100 / 100	956 ms	8204 KiB

simurgh

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

#define vi vector<int>
#define pb push_back
#define ccr count_common_roads

const int mN=500, mM=124750;
int n, tin[mN], low[mN], dt=1, b[mM], bs, st[mM], sth, t[mN], p[mN], c[mN];
vi eu, ev, adj[mN], ans;

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[v]>=tin[u]) {
				do {
					b[st[--sth]]=bs;
				} while(st[sth]^e);
				++bs;
			}
		} else if(v^p&&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;
}

void fst(vi w, vi &r) {
	for(int i=0; i<eu.size(); ++i)
		if(w[i]&&join(eu[i], ev[i]))
			r.pb(i);
}

void dc(vi &a, vi &b, vi &c, int l, int r, int s1, int s2) {
	if(s2==s1)
		return;
	if(l==r) {
		c.pb(b[l]);
		return;
	}
	int m=(l+r)/2;
	vi d=a;
	for(int i=l; i<=m; ++i)
		d[i]=b[i];
	int sl=ccr(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, int pe=-1) {
	vi v1, v2, r;
	for(int e : adj[u]) {
		int v=eu[e]^ev[e]^u;
		if(c[v])
			continue;
		if(t[v]<0) {
			v2.pb(e);
			t[v]=e;
		} else
			v1.pb(e);
	}
	if(v1.size()) {
		iota(p, p+n, 0);
		vi s1, w(eu.size(), 1), s2=v1;
		for(int i=0; i<v1.size(); ++i) {
			s1.pb(t[eu[v1[i]]^ev[v1[i]]^u]);
			join(eu[s1.back()], ev[s1.back()]);
		}
		for(int e : ans) {
			s1.pb(e);
			join(eu[e], ev[e]);
		}
		for(int e : v1) {
			w[e]=0;
			w[t[eu[e]^ev[e]^u]]=0;
		}
		fst(w, s1);
		s2.insert(s2.end(), s1.begin()+v1.size(), s1.end());
		dc(s1, v1, r, 0, v1.size()-1, ccr(s1), ccr(s2));
	}
	if(v2.size()) {
		vi w(eu.size(), 1), s;
		for(int e : adj[u])
			w[e]=0;
		iota(p, p+n, 0);
		fst(w, s);
		for(int e : r)
			if(join(eu[e], ev[e]))
				s.pb(e);
		if(~pe&&join(eu[pe], ev[pe]))
			s.pb(pe);
		for(int e : adj[u])
			if(join(eu[e], ev[e]))
				s.pb(e);
		int bc=ccr(s);
		sort(v2.begin(), v2.end(), [](const int &i, const int &j) {
			return b[i]<b[j];
		});
		for(int i=0, j=0, o; i<v2.size(); ) {
			for(; j<v2.size()&&b[v2[j]]==b[v2[i]]; ++j);
			for(int e : s)
				if(b[e]==b[v2[i]]&&(eu[e]==u||ev[e]==u))
					o=e;
			s.erase(find(s.begin(), s.end(), o));
			vi a;
			int cm=bc;
			for(; i<j; ++i) {
				s.pb(v2[i]);
				int cc=ccr(s);
				if(cc>cm) {
					cm=cc;
					a=vector<int>();
				}
				if(cc==cm)
					a.pb(v2[i]);
				s.pop_back();
			}
			s.pb(o);
			r.insert(r.end(), a.begin(), a.end());
		}
	}
	for(int e : r) {
		ans.pb(e);
		c[eu[e]^ev[e]^u]=1;
	}
	for(int e : r)
		dfs2(eu[e]^ev[e]^u, e);
}

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

Compilation message (stderr)

simurgh.cpp: In function 'void fst(std::vector<int>, std::vector<int>&)':
simurgh.cpp:46: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, int)':
simurgh.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v1.size(); ++i) {
                ~^~~~~~~~~~
simurgh.cpp:116:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0, j=0, o; i<v2.size(); ) {
                        ~^~~~~~~~~~
simurgh.cpp:117: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:151:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<u.size(); ++i) {
               ~^~~~~~~~~

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