제출 #381022

#제출 시각아이디문제언어결과실행 시간메모리
381022parsabahrami열대 식물원 (Tropical Garden) (IOI11_garden)C++17
49 / 100
155 ms26732 KiB
#include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; #define SZ(x) (int) x.size() #define F first #define S second const int N = 3e5 + 10; int n, m, q, cnt[2], mn[N], M[2][N], C[2][N], out[N], dp[2][N]; vector<int> adj[N]; int cycDFS(int v, int t) { if (C[t][v]) return 0; if (M[t][v]) { C[t][v] = 1; return 1; } M[t][v] = 1; int u = out[v]; return C[t][v] = cycDFS(u, t); } void BFS(int st) { int *pd = dp[st >= n]; fill(pd, pd + N, 1e9 + 1); pd[st] = 0; queue<int> Q; Q.push(st); while (SZ(Q)) { int v = Q.front(); Q.pop(); for (int u : adj[v]) if (pd[u] > pd[v] + 1) pd[u] = pd[v] + 1, Q.push(u); } } inline int check(int p, int v, int x) { if (dp[p >= n][v] > x) return 0; int tmp = (!C[p >= n][p] ? 1e9 + 1 : cnt[p >= n]); int f = !((x - dp[p >= n][v]) % tmp); return f; } void count_routes(int _n, int _m, int P, int R[][2], int _q, int G[]) { n = _n, m = _m, q = _q; fill(mn, mn + N, 1e9); for (int i = 0; i < m; i++) { adj[R[i][0]].push_back(i), mn[R[i][0]] = min(mn[R[i][0]], i); adj[R[i][1]].push_back(i), mn[R[i][1]] = min(mn[R[i][1]], i); } for (int i = 0; i < n * 2; i++) { if (i >= n) { int v = R[mn[i - n]][0] ^ (i - n) ^ R[mn[i - n]][1]; if (mn[i - n] == mn[v]) out[i] = v; else out[i] = v + n; } else { int sec = -1; for (int id : adj[i]) if (id != mn[i]) { sec = id; break; } if (!~sec) sec = mn[i]; int v = R[sec][0] ^ i ^ R[sec][1]; if (sec == mn[v]) out[i] = v; else out[i] = v + n; } } cycDFS(P, 0); cycDFS(P + n, 1); for (int i = 0; i < 2 * n; i++) cnt[0] += C[0][i], cnt[1] += C[1][i]; for (int i = 0; i < n; i++) adj[i] = {}; for (int i = 0; i < 2 * n; i++) adj[out[i]].push_back(i); BFS(P), BFS(P + n); for (int _ = 0; _ < q; _++) { int x = G[_], f = 0; for (int i = n; i < 2 * n; i++) { f += (check(P, i, x) || check(P + n, i, x)); } answer(f); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...