제출 #1041960

#제출 시각아이디문제언어결과실행 시간메모리
1041960vjudge1열대 식물원 (Tropical Garden) (IOI11_garden)C++17
49 / 100
331 ms94292 KiB
#include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> using namespace std; void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { vector<vector<int>> adj(N); for (int i = 0; i < M; ++i) { adj[R[i][0]].push_back(R[i][1]); adj[R[i][1]].push_back(R[i][0]); } set<pair<int,int>> nodes; for (int i = 0; i < N; ++i) { nodes.insert({-1, i}); for (int v : adj[i]) nodes.insert({i, v}); } map<pair<int,int>,int> idx; map<int,pair<int,int>> inv; int idx_ = 0; for (auto node : nodes) { idx[node] = idx_; inv[idx_] = node; ++idx_; } int siz = nodes.size(); const int J = 30; vector<vector<int>> succ(siz, vector<int>(J+1, -1)); for (int i = 0; i < N; ++i) { succ[idx[{-1, i}]][0] = idx[{i, adj[i][0]}]; for (int v : adj[i]) { if (v != adj[i][0]) succ[idx[{v, i}]][0] = idx[{i, adj[i][0]}]; else succ[idx[{v, i}]][0] = idx[{i, adj[i][1]}]; } } for (int j = 1; j <= J; ++j) { for (int u = 0; u < siz; ++u) { succ[u][j] = succ[ succ[u][j-1] ][j-1]; } } for(int it = 0; it < Q; ++it) { int K = G[it]; int cnt = 0; for (int i = 0; i < N; ++i) { int u = idx[{-1, i}]; int k = K; for (int j = J; j >= 0; --j) { if (k & (1 << j)) { k -= 1 << j; u = succ[u][j]; } } auto node = inv[u]; if (node.second == P) ++cnt; } answer(cnt); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...