제출 #111740

#제출 시각아이디문제언어결과실행 시간메모리
111740zscoderBitaro’s Party (JOI18_bitaro)C++14
14 / 100
2058 ms217752 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<int,int> ii; typedef vector<int> vi; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<ll>::iterator sit; typedef map<ll,ll>::iterator mit; const int C = 180; vi adj[111111]; vi radj[111111]; vector<ii> dp[111111]; int n,m,q; bool isbad[111111]; void solve_large(int u) { int ans = -1; vi innerdp(n+1,-1); innerdp[u] = 0; for(int i=u;i>=0;i--) { for(int v:adj[i]) { if(innerdp[v]!=-1) innerdp[i] = max(innerdp[i], innerdp[v] + 1); } if(!isbad[i]) ans = max(ans, innerdp[i]); } cout<<ans<<'\n'; } bool appeared[111111]; vector<ii> mergevector(vector<ii> &v1, vector<ii> &v2) { vector<ii> V; vi A; int p1 = 0; int p2 = 0; while((p1<v1.size()||p2<v2.size())&&V.size()<C+1) { int val1 = -100000; int val2 = -100000; if(p1<v1.size()) val1 = v1[p1].fi; if(p2<v2.size()) val2 = v2[p2].fi+1; if(val1>val2) { V.pb(mp(val1, v1[p1].se)); appeared[v1[p1].se]=1;A.pb(v1[p1].se); p1++; } else { V.pb(mp(val2, v2[p2].se)); appeared[v2[p2].se]=1;A.pb(v2[p2].se); p2++; } while(p1<v1.size()&&appeared[v1[p1].se]) p1++; while(p2<v2.size()&&appeared[v2[p2].se]) p2++; } for(int x:A) appeared[x]=0; return V; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>q; for(int i=0;i<m;i++) { int u, v; cin>>u>>v;u--;v--; adj[u].pb(v); radj[v].pb(u); } for(int i=0;i<n;i++) { dp[i].pb(mp(0,i)); for(int v:radj[i]) { dp[i] = mergevector(dp[i], dp[v]); } /* cerr<<"DP "<<i<<'\n'; for(ii x:dp[i]) { cerr<<x.fi<<' '<<x.se<<'\n'; } */ } for(int i=0;i<q;i++) { int u; cin>>u; u--; int k; cin>>k; vi vec; for(int j=0;j<k;j++) { int v; cin>>v; v--; vec.pb(v); } for(int v:vec) isbad[v]=1; if(k>=C-1) { solve_large(u); } else { int ans = -1; for(ii x:dp[u]) { if(isbad[x.se]) continue; ans = max(ans, x.fi); } cout<<ans<<'\n'; } for(int v:vec) isbad[v]=0; } }

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

bitaro.cpp: In function 'std::vector<std::pair<int, int> > mergevector(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:52:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((p1<v1.size()||p2<v2.size())&&V.size()<C+1)
         ~~^~~~~~~~~~
bitaro.cpp:52:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((p1<v1.size()||p2<v2.size())&&V.size()<C+1)
                       ~~^~~~~~~~~~
bitaro.cpp:55:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p1<v1.size()) val1 = v1[p1].fi;
      ~~^~~~~~~~~~
bitaro.cpp:56:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p2<v2.size()) val2 = v2[p2].fi+1;
      ~~^~~~~~~~~~
bitaro.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1<v1.size()&&appeared[v1[p1].se]) p1++;
         ~~^~~~~~~~~~
bitaro.cpp:70:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p2<v2.size()&&appeared[v2[p2].se]) p2++;
         ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...