| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 775577 |
2023-07-06T14:21:43 Z |
hgmhc |
None (JOI16_ho_t3) |
C++17 |
|
65 ms |
14584 KB |
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x),end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define fi first
#define se second
using namespace std; using ll = long long; using ii = pair<int,int>;
template <const int N>
struct disjoint_set {
int p[N], s[N];
vector<int> lazy[N];
disjoint_set(){ fill(s,s+N,1), iota(p,p+N,0); }
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
bool same(int a, int b){ return find(a)==find(b); }
void merge(int a, int b) {
a = find(a), b = find(b);
assert(a!=b);
if (s[a]+siz(lazy[a])>s[b]+siz(lazy[b])) swap(a,b);
s[b]+=s[a];
lazy[b].insert(end(lazy[b]),all(lazy[a]));
lazy[a].clear();
p[a]=b;
}
void lazy_push(int x, int y) {
lazy[find(x)].push_back(y);
}
void lazy_pop(int x) {
x = find(x);
while (not empty(lazy[x])) {
vector<int> lazy_here;
for (auto y : lazy[x]) {
y = find(y);
if (not same(x,y)) {
lazy_here.insert(end(lazy_here),all(lazy[y]));
lazy[y].clear();
}
}
for (auto y : lazy[x]) if (not same(x,y)) merge(x,y);
lazy[x].clear();
x = find(x);
lazy[x] = lazy_here;
}
}
int size(int x){ return s[find(x)]; }
};
const int N = 1e5+3, M = 2e5+3, Q = M;
int n, m, q;
ii edge[M];
vector<ii> adj[N];
int r[Q], ans[Q];
disjoint_set<N> ds;
bool active[M], invalid[M];
int dist[N];
void bfs_to_make_DAG() {
bool vis[N]{};
queue<int> q;
q.push(1), dist[1] = 0, vis[1] = true;
while (not empty(q)) {
int s = q.front(); q.pop();
for (auto [i,u] : adj[s]) {
if (vis[u]) {
if (abs(dist[u]-dist[s])!=1) {
invalid[i] = true;
}
continue;
}
vis[u] = true;
dist[u]=dist[s]+1;
q.push(u);
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
rep(i,1,m) {
cin >> edge[i].fi >> edge[i].se;
adj[edge[i].fi].push_back({i,edge[i].se});
adj[edge[i].se].push_back({i,edge[i].fi});
}
bfs_to_make_DAG();
fill(active,active+M,true);
rep(i,1,q) cin >> r[i], active[r[i]] = false;
rep(i,1,m) {
if (active[i] and not invalid[i]) {
auto [u,v] = edge[i];
if (not ds.same(u,v))
ds.merge(u,v);
}
}
per(i,1,q) {
// rep(j,1,n) if (ds.same(1,j)) dbg("%d ", j);
// dbg("\n");
ans[i] = n-ds.size(1);
if (i > 1 and not invalid[r[i]]) {
auto [u,v] = edge[r[i]];
if (not ds.same(u,v)) {
if (dist[u]>dist[v]) swap(u,v);
if (ds.same(1,u)) {
if (not ds.same(u,v)) ds.merge(u,v);
} else {
ds.lazy_push(u,v);
}
}
ds.lazy_pop(1);
// dbg("(%d,%d)\n", u,v);
}
}
rep(i,1,q) cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6100 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6100 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
14584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6100 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
