Submission #282521

#	Time	Username	Problem	Language	Result	Execution time	Memory
282521		Noam13	Simurgh (IOI17_simurgh)	C++14	51 / 100	152 ms	4100 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define ii pair<int, int>
#define x first
#define y second
#define vii vector<ii>
#define vvii vector<vii>
#define pb push_back
#define all(x) x.begin(), x.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;

int n, m;
vvii g;
vi check;
vi base;
void dfs(int cur, int c){
	check[cur] = c;
	for(auto nei:g[cur]){
		if (check[nei.x]!=0) continue;
		base.pb(nei.y);
		dfs(nei.x, c);
	}
}
int ask(vi& vec){
	//cout<<"QUERY: "<<endl;
	//for(auto x:vec) cout<<x<<" ";
	int v = count_common_roads(vec);
	//cout<<" =" <<v<<endl;
	return v;
}
vi find_roads(int nn, vi u, vi v) {
	n = nn, m = u.size();
	g.resize(n); check.resize(n);
	loop(i,0,m){
		int a = u[i], b = v[i];
		g[a].pb({b,i});
		g[b].pb({a,i});
	}
	queue<int> q; 
	q.push(0); check[0] = -1;
	vi res;
	while(res.size()<n-1){
		int cur = q.front(); q.pop();
		base = res;
		loop(i,0,n) if(check[i]>=0) check[i] = 0;
		int c = 1;
		loop(i,0,n) if(check[i]==0){
			dfs(i, c++);
		}
		loop(i,0,n) if(check[i]>=0) check[i]--;
		c--;
		vvii buckets(c);
		loop(cur, 0, n) if (check[cur]==-1){
			for(auto nei:g[cur]) if(check[nei.x]>=0){
				buckets[check[nei.x]].pb({nei.y, nei.x});
			}
		}
		loop(i,0,n) if (check[i]==-1) check[i]=-2;
		loop(i,0,c){
			vi vec = base;
			loop(j,0,c) if(j!=i)  vec.pb(buckets[j][0].x);
			int m = buckets[i].size();
			vi vals(m);
			int mx = -1;
			loop(j,0,m){
				vec.pb(buckets[i][j].x);
				vals[j] = ask(vec);
				chkmax(mx, vals[j]);
				vec.pop_back();
			}
			loop(j,0,m){
				if (vals[j]==mx){ //golden road
					ii tmp = buckets[i][j];
					res.pb(tmp.x);
					//q.push(tmp.y);
					check[tmp.y] = -1;
				}
			}
		}
	}
	/*for(auto x:res) cout<<x<<" ";
	cout<<endl;*/
	return res;
}
/*
clear
g++ simurgh.cpp grader.cpp -o a ; ./a
4 6
0 1
0 2
0 3
1 2
1 3
2 3
5 1 0

*/

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:49:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |  while(res.size()<n-1){
      |        ~~~~~~~~~~^~~~
simurgh.cpp:50:7: warning: unused variable 'cur' [-Wunused-variable]
   50 |   int cur = q.front(); q.pop();
      |       ^~~

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