| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 781359 |
2023-07-13T04:13:53 Z |
OrazB |
Simurgh (IOI17_simurgh) |
C++14 |
|
1 ms |
340 KB |
#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
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;
| ~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
