| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 237375 |
2020-06-06T09:33:53 Z |
lyc |
Simurgh (IOI17_simurgh) |
C++14 |
|
10 ms |
6528 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
using vi = vector<int>;
const int mxN = 505;
const int mxM = (500*499)/2 + 10;
const int mxQ = 8000;
int N, M, q = 0;
int U[mxM], V[mxM];
vector<int> al[mxN];
vector<int> span;
int golden[mxM];
struct UnionFind {
vector<int> pa, sz; int comp;
UnionFind(int n) { pa.assign(n,0); iota(ALL(pa),0); sz.assign(n,0); comp = n;}
int findset(int i) { return (i == pa[i]) ? i : (pa[i] = findset(pa[i])); }
bool unionset(int i, int j) {
int x = findset(i), y = findset(j);
if (x != y) {
--comp;
if (sz[x] < sz[y]) swap(x,y);
sz[x] += sz[y], pa[y] = x;
return true;
} return false;
}
};
int ask(vector<int> edges, bool sub=false) {
//assert(++q <= mxQ);
UnionFind UF(N);
for (int e : edges) {
int u = U[e], v = V[e];
assert(UF.unionset(u,v));
UF.unionset(u,v);
}
int cnt = 0;
for (int e : span) if (UF.unionset(U[e],V[e])) {
edges.push_back(e);
cnt += (golden[e] == 1);
}
assert(UF.comp == 1);
return count_common_roads(edges) - (sub ? cnt : 0);
}
int pa[mxN], pre[mxN], low[mxN], dfc, dfr;
vi ears[mxM];
int esz = 0;
vi* cur[mxN];
vector<vi*> decomp;
void dfs(int u, int p) {
pre[u] = low[u] = dfc++;
vector<vi*> vec;
for (int e : al[u]) {
int v = U[e]^V[e]^u;
if (v == p) continue;
if (pre[v] == -1) {
pa[v] = e;
dfs(v,u);
span.push_back(e);
if (low[v] > pre[u]) { // bridge
golden[e] = 1;
if (cur[v] != nullptr) decomp.push_back(cur[v]);
} else {
low[u] = min(low[u],low[v]);
cur[v]->push_back(e);
vec.push_back(cur[v]);
}
} else if (pre[v] < pre[u]) {
low[u] = min(low[u],pre[v]);
ears[esz] = {v,e};
vec.push_back(&ears[esz++]);
}
}
int fst = 0;
cur[u] = nullptr;
for (vi* x : vec) {
int d = pre[*x->begin()];
if (d > low[u] || (d == low[u] && ++fst > 1)) decomp.push_back(x);
else cur[u] = x;
}
if (u == dfr) decomp.push_back(cur[u]);
}
void solve(vi* ear) {
//{cout << "EAR " << SZ(*ear) << ": ";
//int u = *ear->begin();
//bool fst = 1;
//for (int e : (*ear)) {
// if (fst) fst = 0;
// else u ^= U[e]^V[e];
// cout << u << ' ';
//}
//cout << endl;}
vector<int> x[2];
int u = (*ear)[0], v = u, f = (*ear)[1];
FOR(i,1,SZ(*ear)-1){
int e = (*ear)[i];
if (i > 1) x[golden[e] != -1].push_back(e);
v ^= U[e]^V[e];
}
while (v != u) {
x[golden[pa[v]] != -1].push_back(pa[v]);
v ^= U[pa[v]]^V[pa[v]];
}
if (x[0].empty());
else if (x[1].empty()) {
vector<int> que;
//cout << f << " CASE 1: ";
//for (int& e : x[0]) cout << e << ": " << U[e] _ V[e] << ", ";
//cout << endl;
int mn = N;
FOR(i,0,SZ(x[0])-1){
//TRACE("ask" _ x[0][i] _ "without" _ U[x[0][i]] _ V[x[0][i]]);
swap(x[0][i],f);
int q = ask(x[0]);
swap(x[0][i],f);
que.push_back(q);
mn = min(mn,q);
}
FOR(i,0,SZ(x[0])-1){
golden[x[0][i]] = (que[i] == mn); // removed becomes min
}
} else {
vector<int> edges(x[0]);
FOR(i,1,SZ(x[1])-1) edges.push_back(x[1][i]);
edges.push_back(f);
int r = ask(edges);
FOR(i,0,SZ(x[0])-1){
swap(edges[i],x[1][0]);
int q = ask(edges);
swap(edges[i],x[1][0]);
golden[x[0][i]] = ((golden[x[1][0]] && q == r) || q < r);
}
}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N = n;
M = SZ(u);
FOR(i,0,M-1){
U[i] = u[i], V[i] = v[i];
al[u[i]].push_back(i);
al[v[i]].push_back(i);
}
fill(golden,golden+M,-1);
fill(pre,pre+n,-1); dfc = dfr = 0;
dfs(0,-1);
for (vi* x : decomp) solve(x);
//for (int& e : span) { TRACE(e _ ":" _ U[e]+1 _ V[e]+1 _ golden[e]); }
FOR(i,0,N-1) {
for (;;) {
vector<int> all;
for (int e : al[i]) if (golden[e] == -1) all.push_back(e);
if (all.empty()) break;
if (!ask(all,true)) {
for (int e : all) golden[e] = 0;
break;
}
int lo = -1, hi = SZ(all)-1;
while (hi-lo > 1) {
int mid = (lo+hi)/2;
vector<int> edges;
FOR(i,lo+1,mid) edges.push_back(all[i]);
if (ask(edges,true)) hi = mid;
else lo = mid;
}
golden[all[hi]] = 1;
}
}
vector<int> ans;
FOR(i,0,M-1) if (golden[i] == 1) ans.push_back(i);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3328 KB |
correct |
| 2 |
Correct |
6 ms |
3328 KB |
correct |
| 3 |
Correct |
6 ms |
3200 KB |
correct |
| 4 |
Correct |
6 ms |
3328 KB |
correct |
| 5 |
Correct |
6 ms |
3328 KB |
correct |
| 6 |
Correct |
6 ms |
3328 KB |
correct |
| 7 |
Runtime error |
10 ms |
6528 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3328 KB |
correct |
| 2 |
Correct |
6 ms |
3328 KB |
correct |
| 3 |
Correct |
6 ms |
3200 KB |
correct |
| 4 |
Correct |
6 ms |
3328 KB |
correct |
| 5 |
Correct |
6 ms |
3328 KB |
correct |
| 6 |
Correct |
6 ms |
3328 KB |
correct |
| 7 |
Runtime error |
10 ms |
6528 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3328 KB |
correct |
| 2 |
Correct |
6 ms |
3328 KB |
correct |
| 3 |
Correct |
6 ms |
3200 KB |
correct |
| 4 |
Correct |
6 ms |
3328 KB |
correct |
| 5 |
Correct |
6 ms |
3328 KB |
correct |
| 6 |
Correct |
6 ms |
3328 KB |
correct |
| 7 |
Runtime error |
10 ms |
6528 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
6528 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3328 KB |
correct |
| 2 |
Correct |
6 ms |
3328 KB |
correct |
| 3 |
Correct |
6 ms |
3200 KB |
correct |
| 4 |
Correct |
6 ms |
3328 KB |
correct |
| 5 |
Correct |
6 ms |
3328 KB |
correct |
| 6 |
Correct |
6 ms |
3328 KB |
correct |
| 7 |
Runtime error |
10 ms |
6528 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
