제출 #418171

#제출 시각아이디문제언어결과실행 시간메모리
418171ak2006Bitaro’s Party (JOI18_bitaro)C++14
0 / 100
3 ms588 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vl = vector<ll>; const ll mod = 1e9 + 7,inf = 1e18; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void setIO() { fast; // #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); // #endif } int main() { setIO(); int n,m,q; cin>>n>>m>>q; int SQRT = sqrt(n) + 1; vvi adj(n + 1),radj(n + 1); vector<vector<pair<int,int>>> farthest(n + 1); for (int u = 1;u<=n;u++)farthest[u].pb({0,u}); while (m--){ int u,v; cin>>u>>v; adj[u].pb(v),radj[v].pb(u); } vb vis(n,0); for (int u = 1;u<=n;u++){ for (int v:adj[u]){ int l = 0,r = 0; vector<pair<int,int>>vals; while ((l < farthest[u].size() || r < farthest[v].size()) && vals.size() <= SQRT) { pair<int,int>to; if (l >= farthest[u].size()){ to = {farthest[v][r].first,farthest[v][r].second}; r++; } else if (r >= farthest[v].size()){ to = {farthest[u][l].first + 1,farthest[u][l].second}; l++; } else if (farthest[u][l].first + 1 >= farthest[v][r].first){ to = {farthest[u][l].first + 1,farthest[u][l].second}; l++; } else { to = {farthest[v][r].first,farthest[v][r].second}; r++; } vis[to.second] = 1; while (l < farthest[u].size() && vis[farthest[u][l].second])l++; while (r < farthest[v].size() && vis[farthest[v][r].second])r++; vals.pb(to); } for (auto &i:vals)vis[i.second] = 0; farthest[v] = vals; } } while (q--){ int target,y; cin>>target>>y; vb is(n + 1,false); for (int i = 0;i<y;i++){ int x; cin>>x; is[x] = 1; } if (y != -1){ bool done = false; for (auto it:farthest[target]){ if (!is[it.second]){ cout<<it.first<<'\n'; done = true; break; } } if (!done)cout<<-1<<'\n'; } else{ vl dp(n + 1,-inf); ll ans = -1; dp[target] = 0; for (int u = target - 1;u>=1;u--){ for (int v:adj[u])dp[u] = max(dp[u],dp[v] + 1); if (!is[u])ans = max(ans,dp[u]); } cout<<ans<<'\n'; } } return 0; }

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             while ((l < farthest[u].size() || r < farthest[v].size()) && vals.size() <= SQRT)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:40:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             while ((l < farthest[u].size() || r < farthest[v].size()) && vals.size() <= SQRT)
      |                                               ~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:40:86: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |             while ((l < farthest[u].size() || r < farthest[v].size()) && vals.size() <= SQRT)
      |                                                                          ~~~~~~~~~~~~^~~~~~~
bitaro.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                 if (l >= farthest[u].size()){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:47:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |                 else if (r >= farthest[v].size()){
      |                          ~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 while (l < farthest[u].size() && vis[farthest[u][l].second])l++;
      |                        ~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 while (r < farthest[v].size() && vis[farthest[v][r].second])r++;
      |                        ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...