Submission #64449

#	Time	Username	Problem	Language	Result	Execution time	Memory
64449		IvanC	Simurgh (IOI17_simurgh)	C++17	0 / 100	6 ms	2404 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef vector<int> vi;
 
const int MAXN = 501;
 
int adjMatrix[MAXN][MAXN],isRoyal[MAXN*MAXN],dsu_parent[MAXN],N;
vi arestas_certas,arestas_dsu;
 
int dsu_find(int x){
	if(x == dsu_parent[x]) return x;
	return dsu_parent[x] = dsu_find(dsu_parent[x]);
}
 
void dsu_join(int x,int y){
	x = dsu_find(x);
	y = dsu_find(y);
	if(x == y) return;
	if(x > y) swap(x,y);
	dsu_parent[y] = x;
}
 
void dsu_reset(){
	for(int i = 0;i<N;i++) dsu_parent[i] = i;
}
 
void processa(int x){
 
	dsu_reset();
	arestas_dsu.clear();
 
	for(int i = 0;i<N;i++){
		if(i == x) continue;
		for(int j = 0;j<N;j++){
			if(j == x || adjMatrix[i][j] == -1) continue;
			if(dsu_find(i) != dsu_find(j)){
				dsu_join(i,j);
				arestas_dsu.push_back(adjMatrix[i][j]);
			}
		}
	}
 
	vector<vi> arestas_faltam;
	vi qual_pos;
 
	for(int i = 0;i<N;i++){
		if(i == x || dsu_find(i) != i) continue;
		vi novo_cjt;
		for(int j = 0;j<N;j++){
			if(j == x || adjMatrix[x][j] == -1) continue;
			if(dsu_find(j) == dsu_find(i)) novo_cjt.push_back(adjMatrix[x][j]);
		}
		qual_pos.push_back(arestas_dsu.size());
		arestas_dsu.push_back(novo_cjt[0]);
		arestas_faltam.push_back(novo_cjt);
	}
 
	for(int i = 0;i<arestas_faltam.size();i++){
 
		int maxv = 0,hasZero = 0,hasOne = 0;
		vi resultados;
 
		for(int j = 0;j<arestas_faltam[i].size();j++){
			int k = arestas_faltam[i][j];
			arestas_dsu[qual_pos[i]] = k;
			if(isRoyal[k] == -1){
				resultados.push_back(count_common_roads(arestas_dsu));
			}
			else if(isRoyal[k] == 0 && hasZero == 0){
				hasZero = 1;
				resultados.push_back(count_common_roads(arestas_dsu));
			}
			else if(isRoyal[k] == 1 && hasOne == 0){
				hasOne = 1;
				resultados.push_back(count_common_roads(arestas_dsu));
			}
			maxv = max(maxv,resultados.back());
		}
 
		for(int j = 0;j<arestas_faltam[i].size();j++){
			int k = arestas_faltam[i][j];
			if(isRoyal[k] != -1) continue;
			if(resultados[j] == maxv){
				arestas_certas.push_back(k);
				isRoyal[k] = 1;
			}
			else{
				isRoyal[k] = 0;
			}
		}
 
	}
 
}
 
vi find_roads(int n, vi u, vi v) {
 
 	memset(isRoyal,-1,sizeof(isRoyal));
	memset(adjMatrix,-1,sizeof(adjMatrix));
	N = n;
 
	for(int i = 0;i<u.size();i++){
		adjMatrix[u[i]][v[i]] = i;
		adjMatrix[v[i]][u[i]] = i;
	}
 
	for(int i = 0;i<n;i++) processa(i);
 
	sort(arestas_certas.begin(),arestas_certas.end());
	arestas_certas.erase(unique(arestas_certas.begin(),arestas_certas.end()),arestas_certas.end());
 
	return arestas_certas;
 
}

Compilation message (stderr)

simurgh.cpp: In function 'void processa(int)':
simurgh.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<arestas_faltam.size();i++){
                ~^~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0;j<arestas_faltam[i].size();j++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0;j<arestas_faltam[i].size();j++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:104:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<u.size();i++){
                ~^~~~~~~~~

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