Submission #51013

#	Time	Username	Problem	Language	Result	Execution time	Memory
51013		FLDutchman	Simurgh (IOI17_simurgh)	C++14	100 / 100	318 ms	30336 KiB

simurgh

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

#define FOR(i, l, r) for(int i = l; i < r; i++)
#define pb push_back
#define fst first
#define snd second

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

vi isGolden; // -1 = unknown; 0 = false; 1 = true
vi par, parEdge, height; //Parent in dfs tree
vi tree; // set of edges
vi adj[510];
vi adjidx[510];
vii edges; //Edges: sorted by heigth in tree


void buildTree(int n){
	FOR(i, 0, adj[n].size()){
		int k = adj[n][i];
		if(height[k] == -1){
			par[k] = n;
			parEdge[k] = adjidx[n][i];
			tree.pb(parEdge[k]);
			height[k] = height[n]+1;
			buildTree(k);
		}
	}
}

int queryReplacement(int a, int b){
	FOR(i, 0, tree.size()){
		if(tree[i] == a) {
			tree[i] = b;
			int k = count_common_roads(tree);
			tree[i] = a;
			return k;
		}
	}
}

void detTree(){
	int treecnt = count_common_roads(tree);
	FOR(i, 0, edges.size()){
		auto e = edges[i];
		if(par[e.fst] == e.snd) continue;
		int n = e.fst;
		bool allDet = true, allUndet = true;
		int p = 0;
		while(n != e.snd){
			if(isGolden[parEdge[n]] == -1) allDet = false;
			if(isGolden[parEdge[n]] != -1) { p = parEdge[n]; allUndet = false; }
			n = par[n];
		}


		if(allDet) {
			continue;
		}
		
		n = e.fst;	
		if(allUndet){
			bool dec = false, inc = false;
			while(n != e.snd){
				int q = queryReplacement(parEdge[n], i);
				if(q < treecnt) {dec = true; isGolden[parEdge[n]] = 1;}
				if(q > treecnt) {inc = true; isGolden[parEdge[n]] = 0;}
				n = par[n];
			}
			n = e.fst;
			if(inc) while(n != e.snd) {if(isGolden[parEdge[n]] == -1) isGolden[parEdge[n]] = 1; n = par[n];} 
			else if(dec) while(n != e.snd) {if(isGolden[parEdge[n]] == -1) isGolden[parEdge[n]] = 0; n = par[n];}
			else while(n != e.snd) {isGolden[parEdge[n]] = 0; n = par[n];} 
		} else {
			int k = queryReplacement(p, i);
			int v = k - treecnt + isGolden[p];
			while(n != e.snd){
				if(isGolden[parEdge[n]] == -1){
					int t = queryReplacement(parEdge[n], i);
					isGolden[parEdge[n]] = treecnt + v - t;
				}
				n = par[n];
			}
		}
	}

	for(int e : tree){
		if(isGolden[e] == -1) isGolden[e] = 1;
	}
}
vi ufp;

int find(int a) {return ufp[a] = ufp[a] == a ? a : find(ufp[a]);}
void comb(int a, int b) {ufp[find(a)] = ufp[find(b)];}

int queryForest(vi forest){
	ufp.clear();
	FOR(i, 0, tree.size()+1) ufp.pb(i);
	for(int e : forest){
		comb(edges[e].fst, edges[e].snd);
	}
	int treeVal = 0;
	for(int e : tree){
		if(find(edges[e].fst) != find(edges[e].snd)){
			treeVal += isGolden[e];
			forest.pb(e);
			comb(edges[e].fst, edges[e].snd);
		}
	}

	return count_common_roads(forest) - treeVal;
}

int queryInterval(int n, int lb, int rb){
	vi forest;
	FOR(i, lb, rb){
		if(isGolden[adjidx[n][i]] != 1) forest.pb(adjidx[n][i]);
	}
	return queryForest(forest);
}


vi find_roads(int n, vi u, vi v) {
	par.assign(n, -1); parEdge.assign(n, -1); height.assign(n, -1);
	isGolden.assign(u.size(), -1);
	FOR(i, 0, u.size()) {
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
		adjidx[u[i]].pb(i);
		adjidx[v[i]].pb(i);
	}
	par[0] = height[0] = 0;
	parEdge[0] = -1;
	buildTree(0);
	FOR(i, 0, u.size()) {
		if(height[u[i]] > height[v[i]]) edges.pb({u[i], v[i]});
		else edges.pb({v[i], u[i]});
	}
	
	detTree();
	queue<int> q;
	vi outCount;
	FOR(i, 0, tree.size()+1){
		outCount.pb(queryInterval(i, 0, adj[i].size()));
		if(outCount[i] == 1) q.push(i);
	}
	int c = 0;
	while(!q.empty()){
		int k = q.front(); q.pop();
		if(outCount[k] == 0) continue;
		int lb = 0, rb = adj[k].size();
		while(lb+1 != rb){
			int mb = (lb+rb)/2;
			if(queryInterval(k, lb, mb)) rb = mb;
			else lb = mb;
		}
		isGolden[adjidx[k][lb]] = 1;
		outCount[adj[k][lb]] --;
		outCount[k]--;
		if(outCount[adj[k][lb]] == 1) { q.push(adj[k][lb]);}
	}

	vi t;
	FOR(i, 0, isGolden.size()){
		if(isGolden[i] == 1) t.pb(i);
	}

	
	return t;
}

Compilation message (stderr)

simurgh.cpp: In function 'void buildTree(int)':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:23:6:
  FOR(i, 0, adj[n].size()){
      ~~~~~~~~~~~~~~~~~~~               
simurgh.cpp:23:2: note: in expansion of macro 'FOR'
  FOR(i, 0, adj[n].size()){
  ^~~
simurgh.cpp: In function 'int queryReplacement(int, int)':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:36:6:
  FOR(i, 0, tree.size()){
      ~~~~~~~~~~~~~~~~~                 
simurgh.cpp:36:2: note: in expansion of macro 'FOR'
  FOR(i, 0, tree.size()){
  ^~~
simurgh.cpp: In function 'void detTree()':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:48:6:
  FOR(i, 0, edges.size()){
      ~~~~~~~~~~~~~~~~~~                
simurgh.cpp:48:2: note: in expansion of macro 'FOR'
  FOR(i, 0, edges.size()){
  ^~~
simurgh.cpp: In function 'int queryForest(vi)':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:102:6:
  FOR(i, 0, tree.size()+1) ufp.pb(i);
      ~~~~~~~~~~~~~~~~~~~               
simurgh.cpp:102:2: note: in expansion of macro 'FOR'
  FOR(i, 0, tree.size()+1) ufp.pb(i);
  ^~~
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:130:6:
  FOR(i, 0, u.size()) {
      ~~~~~~~~~~~~~~                    
simurgh.cpp:130:2: note: in expansion of macro 'FOR'
  FOR(i, 0, u.size()) {
  ^~~
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:139:6:
  FOR(i, 0, u.size()) {
      ~~~~~~~~~~~~~~                    
simurgh.cpp:139:2: note: in expansion of macro 'FOR'
  FOR(i, 0, u.size()) {
  ^~~
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:147:6:
  FOR(i, 0, tree.size()+1){
      ~~~~~~~~~~~~~~~~~~~               
simurgh.cpp:147:2: note: in expansion of macro 'FOR'
  FOR(i, 0, tree.size()+1){
  ^~~
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:168:6:
  FOR(i, 0, isGolden.size()){
      ~~~~~~~~~~~~~~~~~~~~~             
simurgh.cpp:168:2: note: in expansion of macro 'FOR'
  FOR(i, 0, isGolden.size()){
  ^~~
simurgh.cpp:151:6: warning: unused variable 'c' [-Wunused-variable]
  int c = 0;
      ^
simurgh.cpp: In function 'int queryReplacement(int, int)':
simurgh.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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