Editorial for Phá đường
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; int n,Q,damaged[100100],q[100100],ans[100100],d[100100],region; int get(int x) { return x==d[x]?x:d[x]=get(d[x]); } int main() { int m,b[100100],c[100100]; cin >> n >> m >> Q; region=n; for (int i=1;i<=n;i++) d[i]=i; for (int i=0;i<m;i++) scanf("%d%d",b+i,c+i); for (int i=0;i<Q;i++) scanf("%d",q+i), damaged[--q[i]]=1; for (int i=0;i<m;i++) if (!damaged[i]) { int x=get(b[i]),y=get(c[i]); if (x!=y) region--, d[x]=y; } for (int i=Q-1;i>=0;i--) { ans[i]=region; int x=get(b[q[i]]),y=get(c[q[i]]); if (x!=y) region--, d[x]=y; } for (int i=0;i<Q;i++) printf("%d\n",ans[i]); }
Code mẫu của happyboy99x
#include<bits/stdc++.h> using namespace std; const int N = 1e5, M = 1e5, Q = 1e5; int p[N], d[Q], u[M], v[M], n, m, q, nset, res[Q]; bool del[M]; void enter() { cin >> n >> m >> q; for(int i = 0; i < m; ++i) cin >> u[i] >> v[i], --u[i], --v[i]; for(int i = 0; i < q; ++i) cin >> d[i], del[--d[i]] = true; } void reset(int n) {for(int i = 0; i < n; ++i) p[i] = i; nset = n;} int getset(int u) {return u == p[u] ? u : p[u] = getset(p[u]);} void joint(int u, int v) {if(getset(u) != getset(v)) p[p[u]]=p[v], --nset;} void solve() { reset(n); for(int i = 0; i < m; ++i) if(!del[i]) joint(u[i], v[i]); for(int i = q-1; i >= 0; --i) res[i] = nset, joint(u[d[i]], v[d[i]]); for(int i = 0; i < q; ++i) cout << res[i] << '\n'; } int main() { ios::sync_with_stdio(false); enter(); solve(); return 0; }
Code mẫu của ladpro98
{$MODE OBJFPC} program QHROAD; uses math; const fi=''; maxn=trunc(1e5)+9; type edge=record x,y:longint; end; var n,m,qq,i,j,x,y,scc:longint; e:array[1..maxn] of edge; q,res,lab:array[1..maxn] of longint; chk:array[1..maxn] of boolean; inp:text; function root(u:longint):longint; begin if lab[u]<=0 then exit(u); result:=root(lab[u]); lab[u]:=result; end; procedure union(u,v:longint); begin if lab[u]<lab[v] then lab[v]:=u else begin if lab[u]=lab[v] then dec(lab[v]); lab[u]:=v; end; end; begin assign(inp,fi);reset(inp); readln(inp,n,m,qq); for i:=1 to m do readln(inp,e[i].x,e[i].y); for i:=1 to qq do readln(inp,q[i]); for i:=1 to qq do chk[q[i]]:=true; scc:=n; for i:=1 to m do if not chk[i] then begin x:=root(e[i].x);y:=root(e[i].y); if x<>y then begin union(x,y); dec(scc); end; end; for i:=qq downto 1 do begin res[i]:=scc; x:=root(e[q[i]].x);y:=root(e[q[i]].y); if x<>y then begin union(x,y); dec(scc); end; end; for i:=1 to qq do writeln(res[i]); end.
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); const int MN = 100111; int lab[MN], nReg, res[MN], eu[MN], ev[MN], query[MN], mark[MN]; int n, m, q; int getRoot(int u) { if (lab[u] < 0) return u; return lab[u] = getRoot(lab[u]); } void merge(int u, int v) { u = getRoot(u); v = getRoot(v); if (u == v) return ; --nReg; int x = lab[u] + lab[v]; if (lab[u] < lab[v]) { lab[u] = x; lab[v] = u; } else { lab[v] = x; lab[u] = v; } } void solve() { FOR(i,1,m) if (!mark[i]) { merge(eu[i], ev[i]); } FORD(i,q,1) { res[i] = nReg; int t = query[i]; merge(eu[t], ev[t]); } FOR(i,1,q) printf("%d\n", res[i]); } int main() { while (scanf("%d%d%d", &n, &m, &q) == 3) { FOR(i,1,n) lab[i] = -1; nReg = n; FOR(i,1,m) { scanf("%d%d", &eu[i], &ev[i]); } memset(mark, 0, sizeof mark); FOR(i,1,q) { scanf("%d", &query[i]); mark[query[i]] = i; } solve(); } return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0; int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } typedef pair<int, int> II; const ld PI = acos(-1.0); const ld eps = 1e-9; const int dr[] = { -1, 0, +1, 0}; const int dc[] = { 0, +1, 0, -1}; const int inf = (int) 1e9 + 5; const ll linf = (ll) 1e16 + 5; const int mod = (ll) (1e9 + 7 + eps); #define ok puts("ok") #define maxn 200005 int n, m, from[maxn], to[maxn], q, id[maxn], flag[maxn], dad[maxn], kq[maxn]; int getdad(int x){ if(dad[x] == x) return x; return dad[x] = getdad(dad[x]); } int main(){ // freopen("in.txt", "r", stdin); ms(flag, 0); scanf("%d %d %d", &n, &m, &q); For(i, 1, n) dad[i] = i; For(i, 1, m) scanf("%d %d", &from[i], &to[i]); For(i, 1, q){ scanf("%d", &id[i]); flag[id[i]] = 1; } int u, v, t; kq[q] = n; For(i, 1, m) if(!flag[i]){ u = getdad(from[i]); v = getdad(to[i]); if(u != v){ kq[q]--; if(u > v) swap(u, v); dad[v] = u; } } Ford(i, q, 2){ kq[i - 1] = kq[i]; t = id[i]; u = getdad(from[t]); v = getdad(to[t]); if(u != v){ kq[i - 1]--; if(u > v) swap(u, v); dad[v] = u; } } For(i, 1, q) printf("%d\n", kq[i]); return 0; }
Code mẫu của skyvn97
program qhroad; uses crt; const max=100100; type edge=record u,v:longint; isq:boolean; end; var a:array[1..max] of edge; up:array[1..max] of longint; qr:array[1..max] of longint; res:array[1..max] of longint; m,n,q,cp:longint; function find(x:integer):integer; begin if up[x]<0 then exit(x); up[x]:=find(up[x]); exit(up[x]); end; function join(a,b:integer):integer; var x,y:integer; begin x:=find(a); y:=find(b); if x=y then exit(0); up[y]:=x; exit(1); end; procedure loadgraph; var i:longint; begin read(n); read(m); read(q); for i:=1 to n do up[i]:=-1; for i:=1 to m do begin read(a[i].u); read(a[i].v); a[i].isq:=false; end; for i:=1 to q do begin read(qr[i]); a[qr[i]].isq:=true; end; cp:=n; end; procedure process; var i:integer; begin for i:=1 to m do if not a[i].isq then cp:=cp-join(a[i].u,a[i].v); for i:=q downto 1 do begin res[i]:=cp; cp:=cp-join(a[qr[i]].u,a[qr[i]].v); end; for i:=1 to q do writeln(res[i]); end; begin // assign(input,'tmp.txt'); reset(input); loadgraph; process; end.
Comments