제출 #1008301

#제출 시각아이디문제언어결과실행 시간메모리
1008301c2zi6열대 식물원 (Tropical Garden) (IOI11_garden)C++14
100 / 100
1868 ms33876 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #include "garden.h" #include "gardenlib.h" void BFS(VVI& gp, int s, VI& dist) { int n = gp.size(); queue<int> q; dist = VI(n, -1); dist[s] = 0; q.push(s); while (q.size()) { int u = q.front(); q.pop(); for (int v : gp[u]) if (v != s) { dist[v] = dist[u]+1; q.push(v); } } } int floyd(int s, VI& gp, VI& cycle) { if (gp[s] == -1) return 0; int cnt = 0; int u = s; int v = s; do { u = gp[u]; v = gp[gp[v]]; } while (u != v); do { u = gp[u]; cycle[u] = true; cnt++; } while (u != v); return cnt; } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { int n = N; int m = M; VVI initgp(n); rep(i, m) { int u = R[i][0]; int v = R[i][1]; initgp[u].pb(v); initgp[v].pb(u); } VI gp(2*n, -1); rep(u, n) {int v; v = initgp[u][0]; if (initgp[v].size() == 1 || initgp[v][0] != u) { gp[u] = v; } else { gp[u] = v+n; } if (initgp[u].size() == 1) continue; v = initgp[u][1]; if (initgp[v].size() == 1 || initgp[v][0] != u) { gp[u+n] = v; } else { gp[u+n] = v+n; } } /*cout << "Expected: ";*/ /*auto erexa = [&](int u, int k) {*/ /* while (k--) u = gp[u];*/ /* return u;*/ /*};*/ /*rep(i, Q) {*/ /* int ans = 0;*/ /* rep(u, n) {*/ /* int x = erexa(u, G[i]);*/ /* if (x == P || x == P+n) ans++;*/ /* }*/ /* cout << ans << " ";*/ /*}*/ /*cout << endl;*/ auto val = [&](int u) { if (u < n) return to_string(u); return to_string(u-n) + "*"; }; VI cycle(2*n); int lng1 = floyd(P, gp, cycle); int lng2 = floyd(P+n, gp, cycle); VVI trans(2*n); rep(u, 2*n) if (gp[u] != -1) trans[gp[u]].pb(u); VI dist1, dist2; BFS(trans, P, dist1); BFS(trans, P+n, dist2); rep(i, Q) { int k = G[i]; int ans = 0; if (cycle[P]) { rep(u, n) if (dist1[u] != -1) { ans += (dist1[u]%lng1 == k%lng1 && k >= dist1[u]); } } else { rep(u, n) { ans += (dist1[u] == k); } } if (gp[P+n] != -1) { if (cycle[P+n]) { rep(u, n) if (dist2[u] != -1) { ans += (dist2[u]%lng2 == k%lng2 && k >= dist2[u]); } } else { rep(u, n) { ans += (dist2[u] == k); } } } answer(ans); } }

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:110:10: warning: variable 'val' set but not used [-Wunused-but-set-variable]
  110 |     auto val = [&](int u) {
      |          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...