| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 732629 |
2023-04-29T06:54:56 Z |
flappybird |
None (JOI16_ho_t3) |
C++17 |
|
115 ms |
21744 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int dis[MAX];
vector<int> adj[MAX];
pii edges[MAX];
int ans[MAX];
int R[MAX];
int p[MAX];
vector<int> st[MAX];
int chk[MAX];
int sum[MAX];
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
void uni(int a, int b, int t = 0) {
a = find(a);
b = find(b);
if (a == b) return;
if (a > b) swap(a, b);
p[b] = a;
if (a == 1) {
for (auto v : st[b]) ans[v] = t;
return;
}
if (st[b].size() > st[a].size()) swap(st[a], st[b]);
for (auto v : st[b]) st[a].push_back(v);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
int i, a, b;
for (i = 1; i <= M; i++) cin >> a >> b, adj[a].push_back(b), adj[b].push_back(a), edges[i] = pii(a, b);
queue<int> q;
q.push(1);
dis[1] = 1;
while (q.size()) {
int t = q.front();
q.pop();
for (auto v : adj[t]) {
if (dis[v]) continue;
dis[v] = dis[t] + 1;
q.push(v);
}
}
for (i = 1; i <= N; i++) p[i] = i, st[i].push_back(i);
for (i = 1; i <= Q; i++) cin >> R[i], chk[R[i]] = 1;
for (i = 1; i <= M; i++) if (!chk[R[i]]) {
auto [a, b] = edges[R[i]];
if (dis[a] > dis[b]) swap(a, b);
if (dis[b] != dis[a] + 1) continue;
uni(a, b, Q + 2);
}
for (i = Q; i >= 1; i--) {
auto [a, b] = edges[R[i]];
if (dis[a] > dis[b]) swap(a, b);
if (dis[b] != dis[a] + 1) continue;
uni(a, b, i);
}
for (i = 2; i <= N; i++) sum[ans[i]]++;
for (i = 1; i <= Q; i++) sum[i] += sum[i - 1];
for (i = 1; i <= Q; i++) cout << sum[i] << ln;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
21744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
