Submission #968550

#TimeUsernameProblemLanguageResultExecution timeMemory
968550antonPrize (CEOI22_prize)C++17
0 / 100
1523 ms547280 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> const int P = 22; struct Tree{ int len; vector<pii> anc; vector<int> dpth; vector<vector<pii>> ch; vector<vector<pii>> bl; pii& get_ch(int u, int v){ int cur= 0; for(int step = (1<<22); step>=1; step/=2){ if(cur+step<ch[u].size()){ if(ch[u][cur+step].first<=v){ cur+=step; } } } return ch[u][cur]; } void dfs(int u, int d){ dpth[u]= d; for(auto v: ch[u]){ dfs(v.first, d+1); } } int root =0; Tree(int sz){ len = sz; anc.resize(sz); ch.resize(sz); dpth.resize(sz); for(int i = 0; i<sz; i++){ cin>>anc[i].first; if(anc[i].first ==-1){ root = i; } else{ anc[i].first--; ch[anc[i].first].push_back({i, 0}); } } for(int i = 0; i<sz; i++){ sort(ch[i].begin(), ch[i].end()); } dfs(root, 0); } void select(int u, int need, vector<int>& s, vector<pii>& queries){ if(need ==s.size()){ return; } if(u!=root){ queries.push_back({anc[u].first, u}); } s.push_back(u); for(auto v: ch[u]){ select(v.first, need, s, queries); } } void build_bl(){ bl.resize(22, vector<pii>(len)); for(int i = 0; i<len; i++){ if(i!=root){ bl[0][i] =anc[i]; } else{ bl[0][i] = {root, 0}; } } for(int p = 1; p<P; p++){ for(int i = 0; i<len; i++){ bl[p][i] = {bl[p-1][bl[p-1][i].first].first, bl[p-1][i].second + bl[p-1][bl[p-1][i].first].second}; } } } int sum_on_path(int u, int v){ if(dpth[u]<dpth[v]){ swap(u, v); } //cout<<"p "<<u<<" "<<v<<endl; int res= 0; for(int step =P-1; step>=0; step--){ if(dpth[bl[step][u].first] >= dpth[v]){ res += bl[step][u].second; u = bl[step][u].first; } } for(int step =P-1; step>=0; step--){ if(bl[step][u].first != bl[step][v].first){ res += bl[step][u].second + bl[step][v].second; u = bl[step][u].first; v = bl[step][v].first; } } return res; } }; signed main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); int n, k, q, t; cin>>n>>k>>q>>t; pair<Tree, Tree> tr = {Tree(n), Tree(n)}; vector<int> selected; vector<pii> queries; tr.first.select(tr.first.root, k, selected, queries); for(auto e: selected){ cout<<e+1<<" "; } cout<<endl; for(auto e: queries){ cout<<"? "<<e.first+1<<" "<<e.second+1<<endl; } cout<<"!"<<endl; cout.flush(); for(auto e: queries){ int a, b, c, d; cin>>a>>b>>c>>d; tr.first.get_ch(e.first, e.second).second = b; tr.first.anc[e.second].second= b; //cout<<"anc "<<e.second<<endl; } tr.first.build_bl(); for(int i = 0; i<t; i++){ int a, b; cin>>a>>b; a--, b--; int r= tr.first.sum_on_path(a, b); cout<<r<<" "<<r<<endl; } cout.flush(); }

Compilation message (stderr)

Main.cpp: In member function 'std::pair<long long int, long long int>& Tree::get_ch(long long int, long long int)':
Main.cpp:19:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             if(cur+step<ch[u].size()){
      |                ~~~~~~~~^~~~~~~~~~~~~
Main.cpp: In member function 'void Tree::select(long long int, long long int, std::vector<long long int>&, std::vector<std::pair<long long int, long long int> >&)':
Main.cpp:59:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         if(need ==s.size()){
      |            ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...