제출 #367884

#제출 시각아이디문제언어결과실행 시간메모리
367884NachoLibre열대 식물원 (Tropical Garden) (IOI11_garden)C++17
0 / 100
1 ms492 KiB
#include <bits/stdc++.h> using namespace std; #define sz(a) ((int)(a).size()) typedef vector<int> vint; typedef vector<vint> vvint; #ifndef wambule #include "garden.h" #include "gardenlib.h" #else void answer(int x) { cout << "[!] " << x << endl; } #endif namespace blob { int p, pp; } void G(int x, int x2[], int x4[], int x5[], int x6[], int x7[], int x8[], int x9[], int &z) { x7[x] = z; ++z; int y = x6[x]; if(x7[y]) { if(x5[y]) { x2[x] = -1; x4[x] = (x4[y] == -1 ? -1 : x4[y] + 1); x9[x] = (x9[y] == -1 ? -1 : x9[y] + 1); x5[x] = 1; } else { if(x7[blob::p] >= x7[y]) { if(x != blob::p) x4[x] = x7[blob::p] - x7[y] + 1; } if(x7[blob::pp] >= x7[y]) { if(x != blob::pp) x4[x] = x7[blob::pp] - x7[y] + 1; } x2[x] = x7[x] - x7[y] + 1; x8[y] = 1; } x5[x] = 1; return; } G(y, x2, x4, x5, x6, x7, x8, x9, z); x2[x] = (x8[y] ? -1 : x2[y]); if(x != blob::p) x4[x] = (x4[y] == -1 ? -1 : x4[y] + 1); if(x != blob::pp) x9[x] = (x9[y] == -1 ? -1 : x9[y] + 1); x5[x] = 1; } void count_routes(int n, int m, int p, int r[][2], int q, int gg[]) { blob::p = p; int pp = p + n; blob::pp = pp; int N = 2 * n; int x2[N], x4[N], x5[N]; int x6[N], x7[N], x8[N], x9[N]; vint v[n]; for(int i = 0; i < N; ++i) { x5[i] = x7[i] = x8[i] = 0; x4[i] = (i == p ? 0 : -1); x9[i] = (i == pp ? 0 : -1); x2[i] = -1; } for(int i = 0; i < m; ++i) { if(sz(v[r[i][0]]) < 2) v[r[i][0]].push_back(r[i][1]); if(sz(v[r[i][1]]) < 2) v[r[i][1]].push_back(r[i][0]); } for(int i = 0; i < n; ++i) { x6[i] = v[i][0]; x6[i + n] = v[i][(sz(v[i]) == 2)]; } for(int i = 0; i < N; ++i) { if(x6[x6[i]] == i || x6[x6[i]] == n + i) { x6[i] = x6[i] + n; } } /// // for(int i = 0; i < N; ++i) { // cout << (i >= n ? i - n : i) << ", " << (i >= n) << " -> " << x6[i] << endl; // } /// int z = 1; for(int i = 0; i < N; ++i) { int x = i; if(!x5[x]) { G(x, x2, x4, x5, x6, x7, x8, x9, z); } } for(int qi = 0; qi < q; ++qi) { int g = gg[qi]; int ap = 0; for(int i = 0; i < n; ++i) { if(x2[p] == -1) { if(x4[i] == g) { ++ap; continue; } } else { if(g >= x4[i]) { if((g - x4[i]) % x2[p] == 0) { ++ap; continue; } } } if(x2[pp] == -1) { if(x9[i] == g) { ++ap; continue; } } else { if(g >= x9[i]) { if((g - x9[i]) % x2[pp] == 0) { ++ap; continue; } } } // cout << "[ O ] " << i << endl; } answer(ap); } } #ifdef wambule int n = 5; int m = 5; int p = 2; int q = 2; int g[] = {3, 1}; int r[][2] = {1, 0, 1, 2, 3, 2, 1, 3, 4, 2}; int main() { ios::sync_with_stdio(0); cin.tie(0); count_routes(n, m, p, r, q, g); return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...