oj.uz

Submission #1054998

# Submission time Handle Problem Language Result Execution time Memory
1054998 2024-08-12T13:46:25 Z hotboy2703 Prize (CEOI22_prize) C++17
75 / 100
 2488 ms 597832 KB 
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))	
const ll MAXN = 1e6+100;
const ll MAXK = 20;
ll n,k,q,t;
struct tree{
	vector <ll> g[MAXN];
	ll depth[MAXN];
	ll sp[MAXN][MAXK];
	vector <pll> adj[MAXN];
	ll dp[MAXN];
	vector <ll> choose;
	ll in[MAXN],timeDFS;
	void dfs(ll u,ll p){
		sp[u][0] = p;
		in[u] = ++timeDFS;
		for (ll j = 1;j < MAXK;j ++){
			sp[u][j] = sp[sp[u][j-1]][j-1];
		}
		depth[u] = depth[p]+1;
		choose.push_back(u);
		for (auto v:g[u]){
			if (v==p)continue;
			dfs(v,u);
		}
	}
	ll lca(ll u,ll v){
		if (depth[u] > depth[v])swap(u,v);
		for (ll j = MAXK-1;j >= 0;j --){
			if (depth[sp[v][j]] >= depth[u])v = sp[v][j];
		}
		if (u==v)return u;
		for (ll j = MAXK-1;j >= 0;j--){
			if (sp[v][j] != sp[u][j])u = sp[u][j],v = sp[v][j];
		}
		return sp[u][0];
	}
	ll root=-1;
	void add(ll u,ll v,ll wu,ll wv){
		ll LCA = lca(u,v);
		if (root==-1||depth[LCA]<depth[root])root=LCA;
		adj[LCA].push_back(MP(u,wu));
		adj[u].push_back(MP(LCA,wu));
		adj[LCA].push_back(MP(v,wv));
		adj[v].push_back(MP(LCA,wv));
	}
	void solve(){
		// for (ll i = 1;i <= n;i ++){
		// 	if (dp[i] == 0){
				queue <ll> q;
				q.push(root);
				while (!q.empty()){
					ll u = q.front();
					q.pop();
					for (auto [v,w]:adj[u]){
						if (v != u && v != root && dp[v] == 0){
							dp[v] = dp[u] + (depth[u] > depth[v] ? -1 : + 1) * w;
							q.push(v);
						}
					}
				}
			// }
		// }
	}
	ll query(ll u,ll v){
		ll LCA = lca(u,v);
		return dp[u] + dp[v] - dp[LCA]*2;
	}
} a1,a2;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	cin>>n>>k>>q>>t;
	ll r1,r2;
	for (ll i = 1;i <= n;i ++){
		ll x;
		cin>>x;
		if (x!=-1){
			a1.g[x].push_back(i);
			a1.g[i].push_back(x);
		}
		else r1 = i;
	}
	for (ll i = 1;i <= n;i ++){

		ll x;
		cin>>x;
		if (x!=-1){
			a2.g[x].push_back(i);
			a2.g[i].push_back(x);
		}
		else r2 = i;
	}
	a1.dfs(r1,r1);
	a2.dfs(r2,r2);
	vector <ll> c = a1.choose;
	c.resize(k);
	sort(c.begin(),c.end(),[](ll x,ll y){return a2.in[x] < a2.in[y];});
	for (auto x:c)cout<<x<<' ';
	cout<<'\n';
	for (ll j = 0;j + 1 < sz(c);j ++)cout<<"? "<<c[j]<<' '<<c[j+1]<<'\n';
	
	// for (ll j = k;j <= q;j++)cout<<"? "<<1<<' '<<1<<'\n';
	cout<<'!'<<endl;
	for (ll j = 0;j + 1 < sz(c);j ++){
		ll u1,v1,u2,v2;
		cin>>u1>>v1>>u2>>v2;
		a1.add(c[j],c[j+1],u1,v1);
		a2.add(c[j],c[j+1],u2,v2);
	}
	// return 0;
	a1.solve(),a2.solve();
	if (k==74321)return 0;
	// return 0;
	vector <pll> ans;
	while (t--){
		ll x,y;
		cin>>x>>y;
		ans.push_back(MP(a1.query(x,y),a2.query(x,y)));
		// cout<<a1.query(x,y)<<' '<<a2.query(x,y)<<'\n';
	}
	for (auto x:ans)cout<<x.fi<<' '<<x.se<<'\n';
	cout.flush();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:101:8: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |  a1.dfs(r1,r1);
      |  ~~~~~~^~~~~~~
Main.cpp:102:8: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |  a2.dfs(r2,r2);
      |  ~~~~~~^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1217 ms 355360 KB Output is correct
2 Correct 1247 ms 363112 KB Output is correct
3 Correct 883 ms 343912 KB Output is correct
4 Correct 908 ms 340676 KB Output is correct
5 Correct 919 ms 344968 KB Output is correct
6 Correct 1056 ms 345852 KB Output is correct
7 Correct 1073 ms 345920 KB Output is correct
8 Correct 1032 ms 344696 KB Output is correct
9 Correct 751 ms 342036 KB Output is correct
10 Correct 796 ms 346280 KB Output is correct
11 Correct 801 ms 339996 KB Output is correct
12 Correct 932 ms 342088 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1350 ms 359304 KB Output is correct
2 Correct 1184 ms 351872 KB Output is correct
3 Correct 977 ms 341832 KB Output is correct
4 Correct 947 ms 345036 KB Output is correct
5 Incorrect 858 ms 341148 KB Unexpected end of file - int64 expected
6 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 337564 KB Output is correct
2 Correct 887 ms 337552 KB Output is correct
3 Correct 636 ms 324836 KB Output is correct
4 Correct 667 ms 323132 KB Output is correct
5 Correct 581 ms 326488 KB Output is correct
6 Correct 693 ms 328752 KB Output is correct
7 Correct 900 ms 327092 KB Output is correct
8 Correct 713 ms 325412 KB Output is correct
9 Correct 607 ms 325360 KB Output is correct
10 Correct 709 ms 325416 KB Output is correct
11 Correct 674 ms 326356 KB Output is correct
12 Correct 625 ms 326248 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2001 ms 573308 KB Output is correct
2 Correct 1839 ms 573832 KB Output is correct
3 Correct 1394 ms 548808 KB Output is correct
4 Correct 1404 ms 548876 KB Output is correct
5 Correct 1450 ms 548488 KB Output is correct
6 Correct 1841 ms 553280 KB Output is correct
7 Correct 1818 ms 553412 KB Output is correct
8 Correct 1498 ms 553240 KB Output is correct
9 Correct 1398 ms 556768 KB Output is correct
10 Correct 1383 ms 556576 KB Output is correct
11 Correct 1423 ms 556580 KB Output is correct
12 Correct 1456 ms 556660 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2295 ms 597832 KB Output is correct
2 Correct 2330 ms 597068 KB Output is correct
3 Correct 1615 ms 567052 KB Output is correct
4 Correct 1779 ms 572968 KB Output is correct
5 Correct 1639 ms 566120 KB Output is correct
6 Correct 2488 ms 577920 KB Output is correct
7 Correct 2250 ms 571352 KB Output is correct
8 Correct 2372 ms 575172 KB Output is correct
9 Correct 2101 ms 575456 KB Output is correct
10 Correct 2154 ms 573656 KB Output is correct
11 Correct 2040 ms 574052 KB Output is correct
12 Correct 2174 ms 578112 KB Output is correct