제출 #218638

#제출 시각아이디문제언어결과실행 시간메모리
218638someone_aaBitaro’s Party (JOI18_bitaro)C++17
14 / 100
1620 ms228460 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define vpii vector<pair<int,int> > using namespace std; const int maxn = 100100; const int block = 200; vector<pair<int,int> > v[maxn]; vector<int>ig[maxn], g[maxn]; vector<int>order; int n, m, q; bool blocked[maxn]; bool visited[maxn]; int dp[maxn]; void dfs(int node) { if(visited[node]) return; visited[node] = true; for(int i:ig[node]) { if(!visited[i]) { dfs(i); } } order.pb(node); } int brute_force(int node) { dfs(node); reverse(order.begin(), order.end()); int result = -1; for(int i=0;i<order.size();i++) { int node=order[i]; for(int i:g[node]) { if(!visited[i]) continue; dp[node] = max(dp[node], dp[i] + 1); } //cout<<node<<": "<<dp[node]<<"\n"; if(!blocked[node]) result = max(result, dp[node]); } memset(dp, 0, sizeof(dp)); memset(visited,false,sizeof(visited)); order.clear(); return result; } bool used_node[maxn]; vpii merge_vector(vpii a, vpii b) { vpii nw; /*cout<<"Merging \n"; for(auto i:a) cout<<i.first<<" at "<<i.second<<"\n"; cout<<"With \n"; for(auto i:b) cout<<i.first<<" at "<<i.second<<"\n";*/ int pb = 0; for(auto i:a) { //cout<<i.first<<" at node "<<i.second<<"\n"; while(pb < b.size() && b[pb].first + 1 > i.first) { if(used_node[b[pb].second]) { pb++; continue; } else { used_node[b[pb].second] = true; nw.pb(mp(b[pb].first +1, b[pb].second)); } pb++; } //cout<<"Here: "<<pb<<"\n"; if(used_node[i.second]) continue; used_node[i.second] = true; nw.pb(i); } while(pb < b.size()) { if(!used_node[b[pb].second]) { used_node[b[pb].second] = true; nw.pb(mp(b[pb].first +1, b[pb].second)); } pb++; } for(auto i:nw) used_node[i.second] = false; while(nw.size() > block) { nw.pop_back(); } return nw; } void preprocess() { for(int node=1;node<=n;node++) { v[node].pb(mp(0, node)); for(int i:ig[node]) { //cout<<"Starting merging "<<node<<" with "<<i<<"\n"; v[node] = merge_vector(v[node], v[i]); /*cout<<"Done merging: \n"; for(auto i:v[node]) { cout<<i.first<<" "<<i.second<<"\n"; }*/ } /*cout<<"Finish "<<node<<": \n"; for(auto i:v[node]) { cout<<i.first<<" "<<i.second<<"\n"; }*/ } } void solve() { int node, qs, x; vector<int>points; cin>>node>>qs; for(int i=0;i<qs;i++) { cin>>x; points.pb(x); blocked[x] = true; } if(qs >= block) { cout<<brute_force(node); for(int i:points) blocked[i] = false; return; } int maxtunnels = -1; for(auto i:v[node]) { if(!blocked[i.second]) maxtunnels = max(maxtunnels, i.first); } cout<<maxtunnels<<"\n"; for(int i:points) blocked[i] = false; } int main() { cin>>n>>m>>q; int a, b; for(int i=0;i<m;i++) { cin>>a>>b; g[a].pb(b); ig[b].pb(a); } preprocess(); while(q--) { solve(); } }

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

bitaro.cpp: In function 'int brute_force(int)':
bitaro.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<order.size();i++) {
              ~^~~~~~~~~~~~~
bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge_vector(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:71:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pb < b.size() && b[pb].first + 1 > i.first) {
            ^
bitaro.cpp:90:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pb < b.size()) {
           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...