| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 250694 |
2020-07-18T18:20:41 Z |
srvlt |
Simurgh (IOI17_simurgh) |
C++14 |
|
1 ms |
896 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n0 = 503, m0 = 125000;
int N, M, used[n0], par[n0], ch[m0], same[m0], ep[m0];
int in[n0], out[n0], T, S;
vector <int> g[n0], V, U, query, back[n0];
set <int> st;
void add(int x) {
st.insert(x);
}
void del(int x) {
st.erase(x);
}
bool ex(int x) {
return st.find(x) != st.end();
}
int ask() {
query.clear();
for (int i : st) query.pb(i);
return count_common_roads(query);
}
void dfs(int v) {
used[v] = 1;
in[v] = ++T;
for (int i : g[v]) {
int to = V[i] ^ U[i] ^ v;
if (used[to]) continue;
par[to] = i;
add(i);
dfs(to);
}
out[v] = T;
}
bool upper(int x, int y) {
return in[x] <= in[y] && out[y] <= out[x];
}
bool cmp(const int & x, const int & y) {
if (x == y) return false;
return upper(ep[y], ep[x]);
}
int get(int v, int k) {
int u = v, res = S;
for (int i = 0; i <= k; i++) {
int j = back[v][i];
int to = V[j] ^ U[j] ^ v;
add(j), del(par[u]);
if (ch[par[u]] == 1) {
res--;
}
u = to;
}
res = ask() - res;
u = v;
for (int i = 0; i <= k; i++) {
int j = back[v][i];
int to = V[j] ^ U[j] ^ v;
del(j), add(par[u]);
}
return res;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
N = n, M = SZ(u), V = v, U = u;
for (int i = 0; i < M; i++)
g[v[i]].pb(i), g[u[i]].pb(i);
memset(& ch, -1, sizeof(ch));
par[0] = -1;
dfs(0);
vector <int> path;
S = ask();
for (int i = 0; i < M; i++) {
if (ex(i)) continue;
int a = v[i], b = u[i];
if (upper(b, a)) swap(a, b);
assert(upper(a, b));
int ok = 0;
path.clear();
while (b != a) {
path.pb(par[b]);
if (ch[par[b]] == -1) ok = 1;
b = v[par[b]] ^ u[par[b]] ^ b;
}
if (!ok) continue;
add(i);
for (int j : path) {
if (ch[i] != -1 && ch[j] != -1) continue;
del(j);
int x = ask();
if (x == S) {
same[j] = 1;
if (ch[j] != -1) ch[i] = ch[j];
} else if (x == S + 1) {
ch[i] = 1;
ch[j] = 0;
} else {
ch[i] = 0;
ch[j] = 1;
}
add(j);
}
del(i);
if (ch[i] == -1) ch[i] = 0;
for (int j : path) {
if (same[j]) ch[j] = ch[i];
same[j] = 0;
}
}
for (int i = 0; i < M; i++)
if (ex(i) && ch[i] == -1) ch[i] = 1;
for (int i = 0; i < N; i++) {
for (int j : g[i]) {
if (!ex(j)) {
int to = v[j] ^ u[j] ^ i;
if (upper(to, i)) {
ep[j] = to;
back[i].pb(j);
}
}
}
sort(all(back[i]), cmp);
int cur = -1, have = 0;
while (true) {
int l = cur, r = SZ(back[i]);
while (l < r - 1) {
int mid = l + r >> 1;
if (get(i, mid) > have) {
r = mid;
} else {
l = mid;
}
}
cur = r;
if (r < SZ(back[i])) {
ch[back[i][r]] = 1;
have++;
} else break;
}
}
vector <int> res;
for (int i = 0; i < M; i++) {
if (ch[i] == -1) ch[i] = 0;
if (ch[i] == 1) res.pb(i);
}
return res;
}
Compilation message
simurgh.cpp: In function 'int get(int, int)':
simurgh.cpp:76:7: warning: unused variable 'to' [-Wunused-variable]
int to = V[j] ^ U[j] ^ v;
^~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:145:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
896 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
896 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
896 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
896 KB |
correct |
| 2 |
Incorrect |
1 ms |
896 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
896 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
