Editorial for Vòng đua xe đạp
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 happyboy99x
#include<bits/stdc++.h> using namespace std; #define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i) const int N = 10000, INF = 1e9, MOD = 1e9; vector<int> g[N], rg[N]; bool vst[2][N], mod[N]; int n, m; void enter() { cin >> n >> m; for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u; --v; g[u].push_back(v); rg[v].push_back(u); } } void bfs(vector<int> g[], int s, bool vst[]) { queue<int> q; q.push(s); fill_n(vst, n, false); vst[s] = true; while(!q.empty()) { int u = q.front(); q.pop(); TR(g[u], v) if(!vst[*v]) q.push(*v), vst[*v] = true; } } int d[N], f[N]; bool detectCycle(int u, int &timed) { d[u] = timed++; TR(g[u], v) if(vst[0][*v] && vst[1][*v]) if(d[*v] == -1 ? detectCycle(*v, timed) : d[u] > d[*v]) return d[u] = INF, true; return d[u] = INF, false; } void dfs(int s, int t) { if(f[s] != -1) return; f[s] = 0; if(s == t) f[s] = 1; else TR(g[s], u) if(vst[0][*u] && vst[1][*u]) { dfs(*u, t); mod[s] |= f[s] + f[*u] >= MOD || mod[*u]; f[s] = (f[s] + f[*u]) % MOD; } } void solve() { bfs(g, 0, vst[0]); bfs(rg, 1, vst[1]); int timed = 0; fill_n(d, n, -1); if(!vst[0][1]) cout << 0 << '\n'; else if(detectCycle(0, timed)) cout << "inf\n"; else { fill_n(f, n, -1); dfs(0, 1); if(mod[0]) cout << setw(9) << setfill('0') << f[0] << '\n'; else cout << f[0] << '\n'; } } int main() { ios::sync_with_stdio(false); enter(); solve(); return 0; }
Code mẫu của RR
const FINP=''; FOUT=''; MAXN=10011; oo=1000000000; type pter=^pt; pt=record u:longint; link:pter; end; var f1,f2:text; a:array[1..maxn] of pter; free:array[1..maxn] of boolean; r,d:array[1..maxn] of longint; c:array[1..maxn] of int64; ncs:array[1..maxn] of boolean; n:longint; procedure inp; var u,v,m,i:longint; last:pter; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); read(f1,n,m); for i:=1 to m do begin read(f1,u,v); last:=a[u]; new(a[u]); a[u]^.u:=v; a[u]^.link:=last; end; close(f1); end; procedure DFS(u:longint); var v:longint; x:pter; begin free[u]:=false; x:=a[u]; while x<>nil do begin v:=x^.u; x:=x^.link; if not free[v] then continue; DFS(v); end; end; procedure predone; var u:longint; x:pter; begin fillchar(free,sizeof(free),true); DFS(1); for u:=1 to n do if not free[u] then begin x:=a[u]; while x<>nil do begin inc(d[x^.u]); x:=x^.link; end; end; end; procedure ans; var i:longint; s:string; begin str(c[2],s); if ncs[2] then for i:=1 to 9-length(s) do write(f2,0); writeln(f2,s); end; procedure solve; var t,w,u,v:longint; x:pter; begin if d[1]>0 then begin writeln(f2,'inf'); exit; end; t:=1; w:=1; r[1]:=1; c[1]:=1; if free[2] then begin writeln(f2,0); exit; end; repeat u:=r[t]; inc(t); x:=a[u]; ncs[u]:=ncs[u] or (c[u] div oo>0); c[u]:=c[u] mod oo; if u=2 then begin ans; exit; end; while x<>nil do begin v:=x^.u; x:=x^.link; if free[v] then continue; c[v]:=int64(c[v])+c[u]; ncs[v]:=ncs[v] or ncs[u]; dec(d[v]); if d[v]=0 then begin inc(w); r[w]:=v; end; end; until t>w; writeln(f2,'inf'); end; begin inp; predone; solve; close(f2); end.
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 + eps); #define ok puts("ok") #define maxn 20005 #define maxe 200005 int last[maxn], last1[maxn], next[maxe], next1[maxe], adj[maxe], adj1[maxe], E = 0; int n, m, level[maxn], que[maxn], f[maxn], d[maxn], color[maxn], danhdau[maxn]; bool flag = true; vector<int> V; void add(int u, int v){ adj[E] = v; next[E] = last[u]; last[u] = E; adj1[E] = u; next1[E] = last1[v]; last1[v] = E++; } int go(int u){ int &res = f[u]; if(res != -1) return res; if(level[u] < 0) return res = 0; if(level[u] == 0) return res = 1; res = 0; for(int e = last[u]; e != -1; e = next[e]){ int v = adj[e]; res += go(v); if(d[v]) d[u] = 1; if(res >= mod) { res -= mod; d[u] = 1; } } return res; } void dfs(int u){ if(color[u]) return; color[u] = 1; for(int e = last[u]; e != -1; e = next[e]){ int v = adj[e]; dfs(v); } V.pb(u); } void dfs1(int u){ if(danhdau[u]) return; danhdau[u] = 1; for(int e = last1[u]; e != -1; e = next1[e]){ int v = adj1[e]; if(!danhdau[v] && level[v] != -1 && color[v]){ flag = false; } } } int main(){ // freopen("in.txt", "r", stdin); scanf("%d %d", &n, &m); int u, v; ms(last, -1); ms(last1, -1); E = 0; ms(level, -1); ms(color, 0); ms(danhdau, 0); Rep(run, m){ scanf("%d %d", &u, &v); add(u, v); } level[2] = 0; int size = 0; que[size++] = 2; Rep(i, size){ u = que[i]; for(int e = last1[u]; e != -1; e = next1[e]){ v = adj1[e]; if(level[v] == -1){ level[v] = level[u] + 1; que[size++] = v; } } } dfs(1); for(int i = sz(V) - 1; i >= 0; i--) if(!danhdau[V[i]]){ dfs1(V[i]); } if(!flag){ cout << "inf" << endl; return 0; } ms(f, -1); ms(d, 0); int res = go(1); if(d[1]) printf("%09d", res); else printf("%d", res); return 0; }
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> #include <vector> #include <queue> using namespace std; typedef vector<int> VI; typedef unsigned int uint; #define maxn 10010 #define pb push_back #define mod 1000000000 int n; VI ke[maxn], ken[maxn]; int dist[maxn], f[maxn]; bool inq[maxn], larger[maxn], dt[maxn], vs[maxn]; queue<int> q; void tinh(int i) { if(i==2) { f[i] = 1; larger[i] = false; return; } if(dt[i]) return; dt[i] = true; f[i] = 0; larger[i] = false; for(uint k=0;k<ke[i].size();++k) { int j = ke[i][k]; tinh(j); f[i] += f[j]; larger[i] |= larger[j]; if(f[i]>=mod) { f[i] -= mod; larger[i] = true; } } } int main() { int u, v, m; scanf("%d%d",&n,&m); for(int i=0;i<m;++i) { scanf("%d%d",&u,&v); ke[u].pb(v); ken[v].pb(u); } vs[1] = true; q.push(1); while(!q.empty()) { int u = q.front(); q.pop(); for(uint k=0;k<ke[u].size();++k) { int v = ke[u][k]; if(!vs[v]) { vs[v] = true; q.push(v); } } } if(!vs[2]) { puts("0"); return 0; } q.push(2); dist[2] = 0; inq[2] = true; bool vc = false; while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; if(dist[u]>n) { vc = true; break; } for(uint k=0;k<ken[u].size();++k) { int v = ken[u][k]; if(dist[v]<dist[u]+1 && vs[v]) { dist[v] = dist[u]+1; if(!inq[v]) { q.push(v); inq[v] = true; } } } } if(vc) puts("inf"); else { tinh(1); if(larger[1]) printf("%09d",f[1]); else printf("%d",f[1]); } //system("pause"); return 0; }
Comments