| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 73513 |
2018-08-28T11:18:07 Z |
SmsS |
Simurgh (IOI17_simurgh) |
C++14 |
|
3 ms |
616 KB |
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
#define for2(a,b,c) for(int a = b; a < c; a++)
#include "simurgh.h"
const int maxn = 510;
int adj[maxn][maxn];
bool seen[maxn];
bool burn[maxn];
int s[maxn*maxn/2];
int h[maxn];
int par[maxn];
vector<int> res;
bool sc = 0;
int cur;
int n;
void dfs(int root){
seen[root] = 1;
for2(i,0,n) if(adj[i][root] != -1){
if(!seen[i]){
h[i] = h[root]+1;
par[i] = root;
if(!sc)res.pb(adj[i][root]);
dfs(i);
}else if(sc && h[i] > h[root]+1){
int x = i;
while(x != root){
int y = par[x];
if(s[adj[x][y]]){
int t = 0;
for2(i,0,n-1) if(res[i] == adj[x][y]) t = i;
res[t] = adj[i][root];
if(count_common_roads(res) == cur-(s[adj[x][y]]==2)) s[adj[i][root]] = 1;
else s[adj[i][root]] = 2;
res[t] = adj[x][y];
break;
}
x = y;
}
if(!s[adj[i][root]]){
int mx = cur;
int mn = cur;
vector<int> c;
x = i;
while(x != root){
int y = par[x];
int t = 0;
for2(i,0,n-1) if(res[i] == adj[x][y]) t = i;
res[t] = adj[i][root];
c.pb(count_common_roads(res));
mx = max(mx,c.back());
mn = min(mn,c.back());
res[t] = adj[x][y];
x = y;
}
int cnt = 0;
x = i;
while(x != root){
int y = par[x];
// cout << x << ' ' << y << endl;
if(c[cnt] != mx && mx != mn){
s[adj[x][y]] = 2;
}else s[adj[x][y]] = 1;
cnt++;
x = y;
}
if(cur != mx && mx != mn){
s[adj[root][i]] = 2;
}else s[adj[root][i]] = 1;
// for2(i,0,8) cout << s[i] << endl;
}
}
}
}
//int par[maxn];
int getpar(int x){
if(par[x] < 0) return x;
return par[x] = getpar(par[x]);
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
int m = u.size();
n = N;
for2(i,0,n) for2(j,0,n) adj[i][j] = -1;
for2(i,0,m) adj[u[i]][v[i]] = adj[v[i]][u[i]] = i;
dfs(0);
cur = count_common_roads(res);
sc = 1;
fill(seen,seen+n,0);
dfs(0);
fill(par,par+n,-1);
vector<int> ans;
for2(i,0,m) if(s[i] == 2){
ans.pb(i);
int x = getpar(v[i]);
int y = getpar(u[i]);
if(x == y) continue;
par[x] = y;
}
for(auto e : res){
int x = getpar(v[e]);
int y = getpar(u[e]);
if(x == y) continue;
par[x] = y;
res.pb(e);
}
// for2(i,0,m) cout << s[i] << endl;
//for2(i,0,m) if(!s[i]) s[i] = 2;
res.clear();
for2(i,0,m) if(s[i] == 2) res.pb(i);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
correct |
| 2 |
Correct |
3 ms |
484 KB |
correct |
| 3 |
Correct |
3 ms |
484 KB |
correct |
| 4 |
Incorrect |
3 ms |
540 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
correct |
| 2 |
Correct |
3 ms |
484 KB |
correct |
| 3 |
Correct |
3 ms |
484 KB |
correct |
| 4 |
Incorrect |
3 ms |
540 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
correct |
| 2 |
Correct |
3 ms |
484 KB |
correct |
| 3 |
Correct |
3 ms |
484 KB |
correct |
| 4 |
Incorrect |
3 ms |
540 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
616 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
correct |
| 2 |
Correct |
3 ms |
484 KB |
correct |
| 3 |
Correct |
3 ms |
484 KB |
correct |
| 4 |
Incorrect |
3 ms |
540 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
