oj.uz

Submission #1054992

# Submission time Handle Problem Language Result Execution time Memory
1054992 2024-08-12T13:45:36 Z hotboy2703 Prize (CEOI22_prize) C++17
75 / 100
 2660 ms 391024 KB 
#include<bits/stdc++.h>
using ll = int;
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 705 ms 257832 KB Output is correct
2 Correct 767 ms 261868 KB Output is correct
3 Correct 541 ms 245904 KB Output is correct
4 Correct 539 ms 245300 KB Output is correct
5 Correct 606 ms 247620 KB Output is correct
6 Correct 750 ms 248380 KB Output is correct
7 Correct 747 ms 248448 KB Output is correct
8 Correct 788 ms 246272 KB Output is correct
9 Correct 538 ms 245440 KB Output is correct
10 Correct 567 ms 247088 KB Output is correct
11 Correct 546 ms 240884 KB Output is correct
12 Correct 570 ms 245428 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 261956 KB Output is correct
2 Correct 747 ms 256744 KB Output is correct
3 Correct 635 ms 244204 KB Output is correct
4 Correct 651 ms 246896 KB Output is correct
5 Incorrect 574 ms 244736 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 563 ms 250252 KB Output is correct
2 Correct 571 ms 250120 KB Output is correct
3 Correct 417 ms 236008 KB Output is correct
4 Correct 441 ms 235952 KB Output is correct
5 Correct 467 ms 235992 KB Output is correct
6 Correct 556 ms 236532 KB Output is correct
7 Correct 584 ms 237968 KB Output is correct
8 Correct 582 ms 237880 KB Output is correct
9 Correct 517 ms 237028 KB Output is correct
10 Correct 455 ms 238392 KB Output is correct
11 Correct 475 ms 236504 KB Output is correct
12 Correct 509 ms 238380 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1872 ms 380724 KB Output is correct
2 Correct 1828 ms 380648 KB Output is correct
3 Correct 1338 ms 351468 KB Output is correct
4 Correct 1473 ms 351940 KB Output is correct
5 Correct 1511 ms 350836 KB Output is correct
6 Correct 1794 ms 354868 KB Output is correct
7 Correct 1791 ms 355932 KB Output is correct
8 Correct 1672 ms 355560 KB Output is correct
9 Correct 1655 ms 356100 KB Output is correct
10 Correct 1537 ms 356792 KB Output is correct
11 Correct 1644 ms 356888 KB Output is correct
12 Correct 1580 ms 356460 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2552 ms 391024 KB Output is correct
2 Correct 2660 ms 390696 KB Output is correct
3 Correct 1639 ms 359376 KB Output is correct
4 Correct 1701 ms 363624 KB Output is correct
5 Correct 1606 ms 358936 KB Output is correct
6 Correct 2259 ms 367196 KB Output is correct
7 Correct 1971 ms 363300 KB Output is correct
8 Correct 2119 ms 365612 KB Output is correct
9 Correct 1887 ms 365924 KB Output is correct
10 Correct 1817 ms 364580 KB Output is correct
11 Correct 1941 ms 364960 KB Output is correct
12 Correct 1821 ms 366616 KB Output is correct