Submission #781821

#	Time	Username	Problem	Language	Result	Execution time	Memory
781821		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], lev[N];
vector<int> E[N], G[N];

void dfs(int nd, int pr, vector<int>&vec, int c){
	par[nd] = pr;
	// lev[nd] = c;
	vis[nd] = 1;
	// G[pr].pb(nd);
	for (auto i : E[nd]){
		if (!vis[i]){
			vec.pb(pos[nd][i]);	
			cur[pos[nd][i]] = 1;
			dfs(i, nd, vec, c+1);
		} 
	}
}

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);
}
void pdf(int nd){
	vis[nd] = 1;
	for (auto i : E[nd]){
		if (!vis[i] and cur[pos[nd][i]]) pdf(i);
	}
}	

bool chk(int n){
	for (int i = 1; i <= n; i++) vis[i] = 0;
	pdf(1);
	for (int i = 1; i <= n; i++) if (!vis[i]) return 0;
	return 1;
}

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, 0);
	int prev = count_common_roads(vec);
	// for (int i = 0; i < u.size(); i++) if (cur[i]) cout << u[i] << " " << v[i] << '\n';
	if (prev == n-1) return vec;
	queue<pii> q;
	for (int i = 1; i <= n; i++){
		for (int j = i+1; j <= n; j++){
			if (pos[i][j] == -1 or cur[pos[i][j]]) continue;
			int a = j, b = par[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;
				q.push({i, j});
				q.push({a, b});
			}else if (prev-1 == x){
				good[a][b] = good[b][a] = 1;
				bad[i][j] = bad[j][i] = 1;
				q.push({a, b});
				q.push({i, j});
			}
		}
	}
	vector<vector<int>> p(n+1, vector<int>(n+1, 0));
	while(!q.empty()){
		int x = q.front().ff, y = q.front().ss;
		q.pop();
		if (p[x][y]) continue;
		// cout << x << " " << y << '\n';
		p[x][y] = p[y][x] = 1;
		if (par[y] == x) swap(x,y);
		if (cur[pos[x][y]]){
			for (int i = 1; i <= n; i++){
				if (pos[x][i] != -1 and !cur[pos[x][i]] and !bad[x][i] and !good[x][i]){
					int num = conv(vec, pos[x][y], pos[x][i]);
					if (prev == num){
						if (bad[x][y]) bad[x][i] = 1;
						if (good[x][y]) good[x][i] = 1;
					}else if (prev+1 == num) good[x][i] = 1;
					else if (prev-1 == num) bad[x][i] = 1;
					bad[i][x] = bad[x][i];
					good[i][x] = good[x][i];
					q.push({i, x});
				}
			}	
		}else{
			for (int i = 0; i < u.size(); i++){
				if (cur[i] and !bad[u[i]][v[i]] and !good[u[i]][v[i]]){
					cur[i] = 0;
					cur[pos[x][y]] = 1;
					if (chk(n)){
						int val = conv(vec, i, pos[x][y]);
						// if (!i and x == 1 and y == 3){
						// 	for (int j = 0; j < u.size(); j++) if (cur[j]) cout << u[j] << " " << v[j] << '\n';
						// 	cout << val << '\n';
						// 	cout << '\n';
						// }
						if (prev == val){
							if (bad[x][y]) bad[u[i]][v[i]] = 1;
							if (good[x][y]) good[u[i]][v[i]] = 1;
						}else if (prev+1 == val) bad[u[i]][v[i]] = 1;
						else if (prev-1 == val) good[u[i]][v[i]] = 1;
						good[v[i]][u[i]] = good[u[i]][v[i]];
						bad[v[i]][u[i]] = bad[u[i]][v[i]];
						q.push({u[i], v[i]});
					}
					cur[i] = 1;
					cur[pos[x][y]] = 0;
				}
			}
		}
	}
	vector<int> ans;
	for (int i = 0; i < u.size(); i++){
		if (!bad[u[i]][v[i]]){
			// assert(!bad[u[i]][v[i]]);
			ans.pb(i);
		}
	}
	assert(ans.size() == n-1);

	// 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:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  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:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0; i < u.size(); i++){
      |                  ~~^~~~~~~~~~
simurgh.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    for (int i = 0; i < u.size(); i++){
      |                    ~~^~~~~~~~~~
simurgh.cpp:131:20: 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 < u.size(); i++){
      |                  ~~^~~~~~~~~~
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:1:
simurgh.cpp:137:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |  assert(ans.size() == n-1);
      |         ~~~~~~~~~~~^~~~~~

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