| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 781818 |
2023-07-13T11:29:19 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], 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);
}
}
// 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: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++){
| ~~^~~~~~~~~~
| # |
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 |
- |
