Submission #865612

#TimeUsernameProblemLanguageResultExecution timeMemory
865612mychecksedadPrize (CEOI22_prize)C++17
0 / 100
401 ms215852 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' const int N = 1e6+100, M = 1e5+10, K = 22, MX = 30; int ask(int i, int j){ cout << "? " << i << ' ' << j << endl; int x,y,z,w; cin >> x >> y >> z >> w; return x; } int n, k, q, t, root1, root2, w[N], par[N], dep[N], dp[N][K], up[N][K], tin[N], tout[N], timer = 0; vector<int> g[N], r[N], comp; void dfs(int v, int d){ if(comp.size() < k){ comp.pb(v); }else return; tin[v] = timer++; dep[v] = d; for(int u: g[v]) dfs(u, d+1); tout[v] = timer++; } bool is_parent(int u, int v){ return tin[u] <= tin[v] && tout[v] <= tout[u]; } int _lca(int u, int v){ if(is_parent(u, v)) return u; if(is_parent(v, u)) return v; for(int j = K - 1; j >= 0; --j) if(!is_parent(up[u][j], v)) u = up[u][j]; return up[u][0]; } void solve(){ cin >> n >> k >> q >> t; for(int i = 1; i <= n; ++i){ int p; cin >> p; up[i][0] = p; if(p != -1) g[p].pb(i); else root1 = i; } for(int i = 1; i <= n; ++i){ int p; cin >> p; if(p != -1) r[p].pb(i); else root2 = i; } dfs(root1, 0); // cout << comp.size() << '\n'; for(int v: comp) cout << v << ' '; cout << endl; for(int v: comp){ if(v != root1){ dp[v][0] = ask(v, up[v][0]); } } cout << "!" << endl; up[root1][0] = root1; for(int j = 1; j < K; ++j){ for(int v: comp){ up[v][j] = up[up[v][j - 1]][j - 1]; dp[v][j] = dp[v][j - 1] + dp[up[v][j - 1]][j - 1]; } } for(;t--;){ int u, v; cin >> u >> v; int ans = 0, lca = _lca(u, v); for(int j = K - 1; j >= 0; --j){ if((dep[u]-dep[lca])&(1<<j)) ans += dp[u][j], u = up[u][j]; if((dep[v]-dep[lca])&(1<<j)) ans += dp[v][j], v = up[v][j]; } cout << ans << ' ' << ans; if(t != 0) cout << '\n'; } cout << endl; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); } // cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:21:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |   if(comp.size() < k){
      |      ~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:90:15: warning: unused variable 'aa' [-Wunused-variable]
   90 |   int tt = 1, aa;
      |               ^~
#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...