제출 #95145

#제출 시각아이디문제언어결과실행 시간메모리
95145szawinisBitaro’s Party (JOI18_bitaro)C++17
14 / 100
2041 ms10460 KiB
/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ #include <bits/stdc++.h> using namespace std; #define long long long const long MOD = 1e9+7, LINF = 1e18 + 1e16; const int INF = 1e9+1; const double EPS = 1e-10; const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; const int MAGIC = 2, N = 1e5+1; class Bitaro { int n, m, q, indeg[N]; vector<int> adj[N]; pair<int,int> dp[N][MAGIC], dp2[N]; bool blocked[N]; void naive() { fill(dp2, dp2+n+1, make_pair(-INF, -1)); for(int u = 1; u <= n; u++) { if(!blocked[u]) dp2[u] = {0, u}; for(int v: adj[u]) if(dp2[v].first + 1 > dp2[u].first) { dp2[u] = {dp2[v].first + 1, dp2[v].second}; } } } void preprocess() { for(int i = 1; i <= n; i++) for(int j = 0; j < MAGIC; j++) dp[i][j] = {-INF, -1}; for(int u = 1; u <= n; u++) { dp[u][0] = {0, u}; for(int v: adj[u]) { pair<int,int> tmp[2*MAGIC]; int i = 0, j = 0, idx = 0; while(idx < 2*MAGIC) { if(j == MAGIC || dp[u][i].first > dp[v][j].first + 1) tmp[idx++] = dp[u][i++]; else { tmp[idx++] = make_pair(dp[v][j].first + 1, dp[v][j].second); ++j; } } unique(tmp, tmp+2*MAGIC, [] (auto p1, auto p2) { return p1.second == p2.second; }); copy(tmp, tmp+MAGIC, dp[u]); } // cout << "dp[u] " << u << endl; // for(int i = 0; i < MAGIC; i++) cout << dp[u][i].first << ' ' << dp[u][i].second << endl; // cout << endl; } } public: void solve(istream &cin, ostream &cout) { cin >> n >> m >> q; for(int i = 0, s, e; i < m; i++) { cin >> s >> e; adj[e].push_back(s); // ++indeg[e]; } preprocess(); for(int i = 0, T, Y; i < q; i++) { cin >> T >> Y; vector<int> ls(Y); for(int j = 0, v; j < Y; j++) { cin >> ls[j]; blocked[ls[j]] = true; } if(Y >= MAGIC) { naive(); cout << (dp2[T].first < 0 ? -1 : dp2[T].first) << '\n'; } else { bool found = false; for(int i = 0; i < MAGIC; i++) if(dp[T][i].second != -1 && !blocked[dp[T][i].second]) { cout << dp[T][i].first << '\n'; found = true; break; } if(!found) cout << -1 << '\n'; } for(int v: ls) blocked[v] = false; } } }; class Solver { public: void solve(std::istream& in, std::ostream& out) { Bitaro *obj = new Bitaro(); obj->solve(in, out); delete obj; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); Solver solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }

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

bitaro.cpp: In member function 'void Bitaro::solve(std::istream&, std::ostream&)':
bitaro.cpp:67:19: warning: unused variable 'v' [-Wunused-variable]
    for(int j = 0, v; j < Y; j++) {
                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...