Submission #781359

#	Time	Username	Problem	Language	Result	Execution time	Memory
781359		OrazB	Simurgh (IOI17_simurgh)	C++14	0 / 100	1 ms	340 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
 
 
const int N = 505;
int par[N], vis[N], pos[N][N], cur[N], good[N][N], bad[N][N];
vector<int> E[N];
 
void dfs(int nd, int pr, vector<int>&vec){
	par[nd] = pr;
	vis[nd] = 1;
	for (auto i : E[nd]){
		if (!vis[i]){
			vec.pb(pos[nd][i]);	
			cur[pos[nd][i]] = 1;
			dfs(i, nd, vec);
		} 
	}
}
 
int conv(vector<int> vec, int x, int y){
	for (int i = 0; i < vec.size(); i++) if (vec[i] == x) vec[i] = y;
	return count_common_roads(vec);
}
 
vector<int> find_roads(int n, vector<int> u, vector<int> v){
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++) pos[i][j] = -1;
	}
	for (int i = 0; i < u.size(); i++){
		u[i]++; v[i]++;
		E[u[i]].pb(v[i]);
		E[v[i]].pb(u[i]);
		pos[u[i]][v[i]] = i;
		pos[v[i]][u[i]] = i;
	}
	vector<int> vec;
	dfs(1, 0, vec);
	int prev = count_common_roads(vec);
	vector<int> ans;
	while(1){
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++){
				if (pos[i][j] == -1 or cur[pos[i][j]] or good[i][j] or bad[i][j]) continue;
				int a = j, b = par[j];
				vector<pii> v;
				while(b and b != i or b != j){
					int x = conv(vec, pos[a][b], pos[i][j]);
					if (prev+1 == x){
						good[i][j] = good[j][i] = 1; 
						bad[a][b] = bad[b][a] = 1;
						for (auto k : v) good[k.ff][k.ss] = good[k.ss][k.ff] = 1;
						break;
					}else if (prev-1 == x){
						good[a][b] = good[b][a] = 1;
						v.pb({i, j});
						for (auto k : v) bad[k.ff][k.ss] = bad[k.ss][k.ff] = 1;
						break;
					}else{
						if (bad[a][b]){
							v.pb({i, j});
							for (auto k : v) bad[k.ff][k.ss] = bad[k.ss][k.ff] = 1;
							break;
						}else if (good[a][b]){
							v.pb({i, j});
							for (auto k : v) good[k.ff][k.ss] = good[k.ss][k.ff] = 1;
							break;
						}else{
							v.pb({a, b});
							a = b;
							b = par[b];
						}
					}
				}
			}
		}
		ans.clear();
		for (int i = 0; i < u.size(); i++){
			if (!bad[u[i]][v[i]]){
				// assert(!bad[u[i]][v[i]]);
				ans.pb(i);
			}
		}
		if (ans.size() == n-1) break;
	}
	// for (auto i : ans) cout << i << " ";
	
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'int conv(std::vector<int>, int, int)':
simurgh.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < vec.size(); i++) if (vec[i] == x) vec[i] = y;
      |                  ~~^~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < u.size(); i++){
      |                  ~~^~~~~~~~~~
simurgh.cpp:52:13: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |     while(b and b != i or b != j){
      |           ~~^~~~~~~~~~
simurgh.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int i = 0; i < u.size(); i++){
      |                   ~~^~~~~~~~~~
simurgh.cpp:89:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |   if (ans.size() == n-1) break;
      |       ~~~~~~~~~~~^~~~~~

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