#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ok puts("ok");
#define whatis(x) cerr << #x << " = " << x << endl;
#define pause system("pause");
#define random (rand() ^ (rand() << 15))
const int N = (int)1e5 + 7;
const int inf = (int)1e9 + 7;
struct T {
vector < int > tree;
int sz;
T() {
sz = 0;
tree.clear();
}
T(int _sz) {
sz = _sz;
tree.resize(4 * sz, 0);
}
void upd(int pos, int val, int v, int tl, int tr) {
if (tl == tr) {
tree[v] = val;
return ;
}
int mid = (tl + tr) >> 1;
if (pos <= mid) {
upd(pos, val, v + v, tl, mid);
} else {
upd(pos, val, v + v + 1, mid + 1, tr);
}
tree[v] = tree[v + v] + tree[v + v + 1];
}
int get(int l, int r, int v, int tl, int tr) {
if (tl == tr) return tl;
if (tree[1] == 0) return -1;
int mid = (tl + tr) >> 1;
if (tree[v + v]) {
return get(l, r, v + v, tl, mid);
} else {
return get(l, r, v + v + 1, mid + 1, tr);
}
}
};
T seg[N];
int n, m, q, t, y, newchain;
vector < int > gr[N];
vector < int > revgr[N];
int used[N], h[N], deg[2][N], u[N], uh[N];
int chain[N], chainpos[N], chainsz[N], pr[N], head[N], was[N];
void dfs(int v) {
u[v] = 1;
for (int to : gr[v]) {
if (!u[to])
dfs(to);
h[v] = max(h[to] + 1, h[v]);
}
}
void buildhld(int v, int curchain, int p) {
int siz = -1;
int bigchild = -1;
uh[v] = 1;
chain[v] = curchain;
pr[v] = p;
chainpos[v] = ++chainsz[curchain];
if (chainsz[curchain] == 1) {
head[curchain] = v;
}
for (int to : gr[v]) {
if (uh[to]) continue;
if (h[to] > siz) {
siz = h[to];
bigchild = to;
}
}
if (bigchild != -1) {
buildhld(bigchild, curchain, v);
}
for (int to : gr[v]) {
if (uh[to]) continue;
buildhld(to, ++newchain, v);
}
}
int getans(int x) {
int ret = -1;
int v = x;
int sum = 0;
int ans = 0;
while (v) {
int chai = chain[v];
int gg = seg[chai].get(1, chainpos[v], 1, 1, chainsz[chai]);
if (gg != -1 && gg <= chainpos[v]) {
// whatis(gg);
ans = sum + (chainpos[v] - gg + 1);
ret = gg;
}
sum += chainpos[v];
v = pr[head[chai]];
}
if (ret == -1) return -1;
return ans - 1;
}
main() {
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
gr[u].pb(v);
deg[0][v]++;
deg[1][u]++;
revgr[v].pb(u);
}
for (int i = 1; i <= n; i++) {
if (!deg[0][i]) {
dfs(i);
buildhld(i, ++newchain, 0);
}
}
for (int i = 1; i <= n; i++) {
if (!was[chain[i]]) {
seg[chain[i]] = T(chainsz[chain[i]]);
}
seg[chain[i]].upd(chainpos[i], 1, 1, 1, chainsz[chain[i]]);
was[chain[i]] = 1;
}
while (q--) {
scanf("%d %d", &t, &y);
vector < int > v;
for (int i = 1; i <= y; i++) {
int x;
scanf("%d", &x);
v.pb(x);
seg[chain[x]].upd(chainpos[x], 0, 1, 1, chainsz[chain[x]]);
}
// solve
int ans = getans(t);
printf("%d\n", ans);
// answer query
for (int to : v) {
seg[chain[to]].upd(chainpos[to], 1, 1, 1, chainsz[chain[to]]);
}
}
}
Compilation message
bitaro.cpp:120:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
bitaro.cpp: In function 'int main()':
bitaro.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &t, &y);
~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:148:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8184 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
8184 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8184 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
8184 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8184 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
8184 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
