Submission #1035083

#TimeUsernameProblemLanguageResultExecution timeMemory
1035083pccPrize (CEOI22_prize)C++17
10 / 100
3564 ms767284 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fs first #define sc second #define ll long long #define pll pair<ll,ll> #define al4 array<ll,4> #define ai4 array<int,4> const int mxn = 1e6+10; const int B = 20; struct Tree{ vector<vector<int>> par; vector<int> dfn; vector<pii> eul; vector<int> dep; vector<vector<int>> edges; int pt = 0; Tree(){} void init(int n){ pt = 0; dfn.clear(); eul = vector<pii>(n); dep = vector<int>(n); edges = vector<vector<int>>(n); par = vector<vector<int>>(n,vector<int>(B,0)); } void add_edge(int a,int b){ edges[a].push_back(b); } void dfs(int now = 1,int fa = 1){ eul[now].fs = ++pt; dfn.push_back(now); par[now][0] = fa; for(int i = 1;i<B;i++)par[now][i] = par[par[now][i-1]][i-1]; for(auto nxt:edges[now]){ if(nxt == par[now][0])continue; par[nxt][0] = now; dep[nxt] = dep[now]+1; dfs(nxt,now); } eul[now].sc = pt; } int LCA(int a,int b){ if(dep[a]<dep[b])swap(a,b); int d = dep[a]-dep[b]; for(int i = B-1;i>=0;i--){ if(d&(1<<i))a = par[a][i]; } for(int i = B-1;i>=0;i--){ if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i]; } return a==b?a:par[a][0]; } }; Tree t1,t2; int rt1,rt2; int N,K,Q,T; int val1[mxn],val2[mxn]; vector<int> tar; vector<pii> req; vector<ai4> res; vector<pii> ans; int C = 0; void ask(int a,int b){ C++; assert(C<=K*2-2); cout<<"? "<<a<<' '<<b<<'\n'; req.push_back(pii(a,b)); res.push_back(ai4({0,0,0,0})); return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin.exceptions(cin.failbit); cin>>N>>K>>Q>>T; t1.init(N+1);t2.init(N+1); for(int i = 1;i<=N;i++){ int p; cin>>p; if(p == -1)rt1 = i; else{ t1.add_edge(p,i); t1.add_edge(i,p); } } for(int i = 1;i<=N;i++){ int p; cin>>p; if(p == -1)rt2 = i; else{ t2.add_edge(p,i); t2.add_edge(i,p); } } t1.dfs(rt1,rt1);t2.dfs(rt1,rt1); for(int i = 0;i<K;i++)tar.push_back(t1.dfn[i]); for(auto &i:tar)cout<<i<<' ';cout<<endl; int s = tar.size(); sort(tar.begin(),tar.end(),[&](int a,int b){return t2.eul[a].fs<t2.eul[b].fs;}); for(int i = 1;i<s;i++)tar.push_back(t2.LCA(tar[i],tar[i-1])); sort(tar.begin(),tar.end(),[&](int a,int b){return t2.eul[a].fs<t2.eul[b].fs;}); tar.resize(unique(tar.begin(),tar.end())-tar.begin()); assert(tar.size()<=K*2-1); for(auto &i:tar){ if(i != rt1){ ask(rt1,i); } } cout<<"!"<<endl; for(int i = 0;i<req.size();i++){ auto [a,b] = req[i]; for(auto &j:res[i])cin>>j; val1[b] = res[i][1]; val2[b] = res[i][2]+res[i][3]; } while(T--){ int a,b; cin>>a>>b; if(a == b)ans.push_back(pll(0,0)); else{ pii tans; tans.fs = 1ll*val1[a]+val1[b]-val1[t1.LCA(a,b)]*2ll; tans.sc = 1ll*val2[a]+val2[b]-val2[t2.LCA(a,b)]*2ll; ans.push_back(tans); } } for(auto &i:ans)cout<<i.fs<<' '<<i.sc<<'\n'; cout<<endl; return 0; } //sig 13 = WA

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:104:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  104 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |  ^~~
Main.cpp:104:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  104 |  for(auto &i:tar)cout<<i<<' ';cout<<endl;
      |                               ^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp:110:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |  assert(tar.size()<=K*2-1);
      |         ~~~~~~~~~~^~~~~~~
Main.cpp:117:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for(int i = 0;i<req.size();i++){
      |                ~^~~~~~~~~~~
#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...