| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 64449 |
2018-08-04T13:44:25 Z |
IvanC |
Simurgh (IOI17_simurgh) |
C++17 |
|
6 ms |
2404 KB |
#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
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++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2296 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2296 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2296 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2404 KB |
correct |
| 2 |
Incorrect |
4 ms |
2404 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2296 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
