oj.uz

Submission #1055001

# Submission time Handle Problem Language Result Execution time Memory
1055001 2024-08-12T13:48:06 Z hotboy2703 Prize (CEOI22_prize) C++17
100 / 100
 2066 ms 597780 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 1150 ms 351704 KB Output is correct
2 Correct 1066 ms 359704 KB Output is correct
3 Correct 772 ms 341580 KB Output is correct
4 Correct 807 ms 347628 KB Output is correct
5 Correct 743 ms 351776 KB Output is correct
6 Correct 1155 ms 344480 KB Output is correct
7 Correct 1133 ms 344092 KB Output is correct
8 Correct 1042 ms 342948 KB Output is correct
9 Correct 873 ms 340308 KB Output is correct
10 Correct 935 ms 343144 KB Output is correct
11 Correct 821 ms 337940 KB Output is correct
12 Correct 978 ms 340932 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 358160 KB Output is correct
2 Correct 1114 ms 354852 KB Output is correct
3 Correct 886 ms 344144 KB Output is correct
4 Correct 886 ms 349004 KB Output is correct
5 Correct 774 ms 350696 KB Output is correct
6 Correct 866 ms 350748 KB Output is correct
7 Correct 1016 ms 354772 KB Output is correct
8 Correct 962 ms 355284 KB Output is correct
9 Correct 881 ms 355668 KB Output is correct
10 Correct 1004 ms 357092 KB Output is correct
11 Correct 860 ms 352052 KB Output is correct
12 Correct 1000 ms 357404 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 344828 KB Output is correct
2 Correct 621 ms 343588 KB Output is correct
3 Correct 517 ms 330592 KB Output is correct
4 Correct 458 ms 330540 KB Output is correct
5 Correct 446 ms 330688 KB Output is correct
6 Correct 549 ms 331264 KB Output is correct
7 Correct 560 ms 332828 KB Output is correct
8 Correct 553 ms 332800 KB Output is correct
9 Correct 509 ms 333816 KB Output is correct
10 Correct 537 ms 333948 KB Output is correct
11 Correct 517 ms 333776 KB Output is correct
12 Correct 545 ms 333560 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1596 ms 575200 KB Output is correct
2 Correct 1608 ms 575364 KB Output is correct
3 Correct 1136 ms 550324 KB Output is correct
4 Correct 1136 ms 550456 KB Output is correct
5 Correct 1124 ms 550528 KB Output is correct
6 Correct 1437 ms 554948 KB Output is correct
7 Correct 1471 ms 555064 KB Output is correct
8 Correct 1480 ms 554956 KB Output is correct
9 Correct 1429 ms 557116 KB Output is correct
10 Correct 1326 ms 556580 KB Output is correct
11 Correct 1357 ms 556552 KB Output is correct
12 Correct 1354 ms 556616 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1974 ms 597780 KB Output is correct
2 Correct 1978 ms 597460 KB Output is correct
3 Correct 1485 ms 567288 KB Output is correct
4 Correct 1435 ms 573200 KB Output is correct
5 Correct 1369 ms 565892 KB Output is correct
6 Correct 2066 ms 578292 KB Output is correct
7 Correct 1869 ms 571140 KB Output is correct
8 Correct 2028 ms 575080 KB Output is correct
9 Correct 1764 ms 575464 KB Output is correct
10 Correct 1803 ms 574160 KB Output is correct
11 Correct 1829 ms 573784 KB Output is correct
12 Correct 1888 ms 577596 KB Output is correct