Submission #803762

#	Time	Username	Problem	Language	Result	Execution time	Memory
803762		ngrace	Simurgh (IOI17_simurgh)	C++14	100 / 100	188 ms	11500 KiB

simurgh

#include "simurgh.h"


#include <bits/stdc++.h>
using namespace std;
#define ve vector
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second

int N;
set<int> ans;

struct DSU{
	int par[500];
	int si=0;
	DSU(int siz){
		si=siz;
		reset();
	}
	void reset(){
		for(int i=0; i<si; i++) par[i]=i;
	}
	int root(int x) {
		return (x==par[x]) ? x : par[x]=root(par[x]);
	}
	void doUnion(int a, int b){
		par[root(a)]=root(b);
	}
};

int edgeInd[500][500];

DSU components(500);
int cutTime=0;
ve<bool> vis(500, false);
ve<int> firstTime(500, -1);
ve<int> lowTime(500, -1);
bool cutEdge[500][500];
void cutDFS(int cur, int par){
	vis[cur]=true;
	firstTime[cur] = lowTime[cur] = cutTime++;
	for(int i=0; i<N; i++){
		if(edgeInd[cur][i]==-1 || i==par) continue;

		if(vis[i]) lowTime[cur] = min(lowTime[cur], firstTime[i]);
		else{
			cutDFS(i, cur);
			lowTime[cur] = min(lowTime[cur], lowTime[i]);
			if(lowTime[i] > firstTime[cur]) {
				cutEdge[cur][i] = cutEdge[i][cur]=true;
			}
		}
	}
}
ve<ii> cutEdges;
void findCutEdges(){
	cutDFS(0, 0);

	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			if(edgeInd[i][j]==-1) continue;
			if(!cutEdge[i][j]){
				components.doUnion(i, j);
			}
			else{
				ans.insert(edgeInd[i][j]);
				cutEdges.push_back({i, j});
			}
		}
	}
}

ve<ii> baseTree;
bool treeVis[500];
void treeDFS(int x){
	treeVis[x]=true;
	for(int i=0; i<N; i++){
		if(edgeInd[x][i]==-1) continue;
		if(!treeVis[i]){
			baseTree.push_back({x, i});
			treeDFS(i);
		}
	}
}

ve<ve<int>> cycs;
bool earEdgeUsed[500][500];
bool inEar[500];
int earVis[500];
int curEarVis=0;
bool debug=false;
bool earDFS(int x, int par){
	if(inEar[x]){
		cycs.back().push_back(x);
		return true;
	}
	if(earVis[x] == curEarVis) return false;
	earVis[x] = curEarVis;
	cycs.back().push_back(x);
	for(int i=0; i<N; i++){
		if(edgeInd[x][i]==-1 || cutEdge[x][i] || i==par) continue;
		if(earDFS(i, x)) return true;
	}
	cycs.back().pop_back();
	return false;
}
ve<ii> knownEdges;
void ear(int start){
	ve<int> nodes = {start};

	cycs.clear();
	while(nodes.size()>0){
		int cur=nodes.back();
		int next=-1;
		for(int i=0; i<N; i++){
			if(edgeInd[cur][i]==-1 || cutEdge[cur][i] || earEdgeUsed[cur][i]) continue;
			next=i;
			break;
		}
		if(next==-1){
			nodes.pop_back();
			continue;
		}
		cycs.push_back({cur});
		inEar[cur]=true;
		curEarVis++;
		earVis[cur]=curEarVis;
		earDFS(next, cur);
		for(int i=0; i<cycs.back().size()-1; i++){
			int a=cycs.back()[i];
			int b=cycs.back()[i+1];
			inEar[a]=true;
			if(!inEar[b]) nodes.push_back(b);
			inEar[b]=true;
			earEdgeUsed[a][b] = earEdgeUsed[b][a] = true;
		}
	}

	ve<ve<int>> adj(N);
	ve<int> vis(N, -1);
	ve<int> par(N, -1);
	ve<bool> foundNode(N,false);
	for(int earInd=0; earInd<cycs.size(); earInd++){
		int s = cycs[earInd][0], e=cycs[earInd].back();

		bool skip=true;
		for(int i=0; i<cycs[earInd].size(); i++){
			if(!foundNode[cycs[earInd][i]]) skip=false;
			foundNode[cycs[earInd][i]] = true;
		}
		if(skip) continue;
		
		//bfs to get from e to s on adj of prev edges:
		queue<ii> q;
		q.push({e, e});
		while(q.size()>0){
			ii cur=q.front();
			q.pop();
			if(vis[cur.fi]==earInd) continue;
			vis[cur.fi]=earInd;
			par[cur.fi] = cur.se;
			if(cur.fi==s) break;
			for(int i:adj[cur.fi]) q.push({i, cur.fi});
		}

		ve<int> cyc;
		int cur=s;
		while(par[cur]!=cur){
			cyc.push_back(par[cur]);
			cur=par[cur];
		}
		reverse(cyc.begin(), cyc.end());
		int cycRedundant = cyc.size();
		for(int i=0; i<cycs[earInd].size(); i++){
			cyc.push_back(cycs[earInd][i]);
		}

		if(false){
			cout<<"Ear "<<earInd<<": ";
			for(int i:cycs[earInd]) cout<<i<<" ";
			cout<<endl;
		}
		if(false){
			cout<<"Cycle (redundant: "<<cycRedundant<<"): ";
			for(int i:cyc) cout<<i<<" ";
			cout<<endl;
		}
		

		//Brute force on the cycle:
		//set up tree:
		ve<int> tree;
		ve<int> treeInd(N);
		DSU inTree(N);
		int missing = cyc.size()-2;
		for(int i=0; i<cyc.size()-1; i++){
			int a=cyc[i], b=cyc[i+1];
			inTree.doUnion(a, b);
			tree.push_back(edgeInd[a][b]);
			treeInd[i] = i;
			if(i==missing){
				treeInd[i] = -1;
				tree.pop_back();
			}
		}
		for(ii it:baseTree){
			if(inTree.root(it.fi)!=inTree.root(it.se)){
				tree.push_back(edgeInd[it.fi][it.se]);
				inTree.doUnion(it.fi, it.se);
			}
		}
		int ma=0;
		ve<int> cou(cyc.size()-1, -1);
		for(int i=0; i<cyc.size()-1; i++){
			int a=cyc[i], b=cyc[i+1];
			if(i!=missing){
				int newa = cyc[missing], newb = cyc[missing+1];
				tree[treeInd[i]] = edgeInd[newa][newb];
				treeInd[missing] = treeInd[i];
				treeInd[i] = -1;
				missing = i;
			}
			cou[i] = count_common_roads(tree);
			ma = max(ma, cou[i]);
		}
		for(int i=0; i<cyc.size()-1; i++){
			int a=cyc[i], b=cyc[i+1];
			if(i==cyc.size()-2) continue;//so get a tree
			if(cou[i]<ma){
				int ind = edgeInd[a][b];
				if(ans.find(ind)==ans.end()) ans.insert(ind);
			}
			knownEdges.push_back({a, b});
		}
		


		for(int i=0; i<cycs[earInd].size()-1; i++){
			int a=cycs[earInd][i], b=cycs[earInd][i+1];
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
	}
}

ve<ii> knownTree;
int deg[500];
void calcDeg(int x){
	DSU con(N);
	ve<int> tree;
	int sub = 0;
	for(int i=0; i<N; i++){
		if(edgeInd[x][i]==-1) continue;
		tree.push_back(edgeInd[x][i]); 
		if(ans.find(edgeInd[x][i]) != ans.end()) sub++;
		con.doUnion(x, i);
	}
	for(ii it:knownTree){
		if(con.root(it.fi) == con.root(it.se)) continue;
		tree.push_back(edgeInd[it.fi][it.se]);
		if(ans.find(edgeInd[it.fi][it.se]) != ans.end()) sub++;
		con.doUnion(it.fi, it.se);
	}
	deg[x] = count_common_roads(tree) - sub;
}

void solve(){
	//with degree one verts, binary search for leaf edge and then remove vert.
	stack<int> s;
	for(int i=0; i<N; i++){
		if(deg[i]==1) s.push(i);
	}

	while(ans.size()<N-1){
		int x = s.top();
		s.pop();
		if(deg[x]==0) continue;

		int l=0, r=N-1;
		while(l<r){
			int m=(l+r)/2;
			
			DSU con(N);
			ve<int> tree;
			int sub = 0;
			for(int i=l; i<=m; i++){
				if(edgeInd[x][i]==-1) continue;
				tree.push_back(edgeInd[x][i]); 
				if(ans.find(edgeInd[x][i]) != ans.end()) sub++;
				con.doUnion(x, i);
			}
			for(ii it:knownTree){
				if(con.root(it.fi) == con.root(it.se)) continue;
				tree.push_back(edgeInd[it.fi][it.se]);
				if(ans.find(edgeInd[it.fi][it.se]) != ans.end()) sub++;
				con.doUnion(it.fi, it.se);
			}


			assert(tree.size()==N-1);

			int count = count_common_roads(tree) - sub;
			if(count >0) r=m;
			else l=m+1;
		}

		ans.insert(edgeInd[l][x]);
		deg[x]--;
		deg[l]--;
		if(deg[l]==1) s.push(l);
	}
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N = n;

	if(n==2){
		ve<int> res = {0};
		return res;
	}

	for(int i=0; i<500; i++){
		for(int j=0; j<500; j++){
			edgeInd[i][j]=-1;
		}
	}
	for(int i=0; i < u.size(); i++){
		edgeInd[u[i]][v[i]] = i;
		edgeInd[v[i]][u[i]] = i;
	}

	findCutEdges();

	treeDFS(0);

	set<int> foundComp;
	for(int i=0; i<N; i++){
		if(foundComp.find(components.root(i))==foundComp.end()){
			foundComp.insert(components.root(i));
			ear(i);
		}
	}

	//now know state of all edges in knownEdges and cutEdges, which together form a tree.
	for(ii it:knownEdges) knownTree.push_back(it);
	for(ii it:cutEdges) knownTree.push_back(it);

	for(int i=0; i<N; i++) calcDeg(i);

	solve();

	ve<int> res;
	for(int i:ans) res.push_back(i);
	return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'void ear(int)':
simurgh.cpp:131:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for(int i=0; i<cycs.back().size()-1; i++){
      |                ~^~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:145:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |  for(int earInd=0; earInd<cycs.size(); earInd++){
      |                    ~~~~~~^~~~~~~~~~~~
simurgh.cpp:149:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |   for(int i=0; i<cycs[earInd].size(); i++){
      |                ~^~~~~~~~~~~~~~~~~~~~
simurgh.cpp:176:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |   for(int i=0; i<cycs[earInd].size(); i++){
      |                ~^~~~~~~~~~~~~~~~~~~~
simurgh.cpp:198:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |   for(int i=0; i<cyc.size()-1; i++){
      |                ~^~~~~~~~~~~~~
simurgh.cpp:216:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |   for(int i=0; i<cyc.size()-1; i++){
      |                ~^~~~~~~~~~~~~
simurgh.cpp:217:8: warning: unused variable 'a' [-Wunused-variable]
  217 |    int a=cyc[i], b=cyc[i+1];
      |        ^
simurgh.cpp:217:18: warning: unused variable 'b' [-Wunused-variable]
  217 |    int a=cyc[i], b=cyc[i+1];
      |                  ^
simurgh.cpp:228:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |   for(int i=0; i<cyc.size()-1; i++){
      |                ~^~~~~~~~~~~~~
simurgh.cpp:230:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |    if(i==cyc.size()-2) continue;//so get a tree
      |       ~^~~~~~~~~~~~~~
simurgh.cpp:240:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |   for(int i=0; i<cycs[earInd].size()-1; i++){
      |                ~^~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'void solve()':
simurgh.cpp:276:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  276 |  while(ans.size()<N-1){
      |        ~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:4:
simurgh.cpp:302:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  302 |    assert(tree.size()==N-1);
      |           ~~~~~~~~~~~^~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:329:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  329 |  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