제출 #1106476

#제출 시각아이디문제언어결과실행 시간메모리
1106476FubuGoldBitaro’s Party (JOI18_bitaro)C++14
7 / 100
2098 ms244808 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 100000; const int BLOCK_SZ = 400; int n,m,q; vector<int> adj[MAXN+1]; // rev_adj vector<pair<int,int>> mx_dis[MAXN+1]; void precomp() { for (int u=1;u<=n;u++) { priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; pq.push(make_pair(0,u)); for (int i=0;i<adj[u].size();i++) { int v = adj[u][i]; vector<pair<int,int>> &vec = mx_dis[v]; for (int j=vec.size()-1;j>=0;j--) { pair<int,int> cur = vec[j]; cur.first++; if (pq.size() < BLOCK_SZ || cur.first > pq.top().first) { if (pq.size() == BLOCK_SZ) pq.pop(); pq.push(cur); } else if (cur.first <= pq.top().first) break; } } while (pq.size()) { // cerr << u << ' ' << pq.top().first << ' ' << pq.top().second << '\n'; mx_dis[u].push_back(pq.top()); pq.pop(); } } } int dp[MAXN+1]; bool no_no[MAXN+1]; int query_big(int id) { memset(dp,-1,sizeof(dp)); for (int i=1;i<=id;i++) { if (!no_no[i]) dp[i] = 0; for (int j=0;j<adj[i].size();j++) { int v = adj[i][j]; if (dp[v] == -1) continue; dp[i] = max(dp[i],dp[v] + 1); } } return dp[id]; } int query(int id) { for (int i=mx_dis[id].size()-1;i>=0;i--) { if (!no_no[mx_dis[id][i].second]) return mx_dis[id][i].first; } if (mx_dis[id].size() < BLOCK_SZ) return -1; return query_big(id); } int main() { cin.tie(0) -> sync_with_stdio(0); cin >> n >> m >> q; for (int i=1;i<=m;i++) { int x,y; cin >> x >> y; adj[y].push_back(x); } precomp(); while (q--) { int t,y; vector<int> c; cin >> t >> y; for (int i=0;i<y;i++) { int x; cin >> x; c.push_back(x); no_no[x] = 1; } cout << query(t) << '\n'; for (int i=0;i<y;i++) no_no[c[i]] = 0; } return 0; }

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

bitaro.cpp: In function 'void precomp()':
bitaro.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for (int i=0;i<adj[u].size();i++) {
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp: In function 'int query_big(int)':
bitaro.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int j=0;j<adj[i].size();j++) {
      |                      ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...