oj.uz

Submission #1054978

# Submission time Handle Problem Language Result Execution time Memory
1054978 2024-08-12T13:38:40 Z hotboy2703 Prize (CEOI22_prize) C++17
29 / 100
 3500 ms 286668 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 = 5e5+100;
const ll MAXK = 19;
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 && 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';
	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();
	// 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 700 ms 194332 KB Output is correct
2 Correct 737 ms 196804 KB Output is correct
3 Correct 547 ms 180924 KB Output is correct
4 Correct 661 ms 181068 KB Output is correct
5 Correct 583 ms 183088 KB Output is correct
6 Correct 751 ms 183816 KB Output is correct
7 Correct 660 ms 183704 KB Output is correct
8 Correct 660 ms 182772 KB Output is correct
9 Correct 560 ms 180544 KB Output is correct
10 Correct 636 ms 182132 KB Output is correct
11 Correct 650 ms 179268 KB Output is correct
12 Correct 692 ms 181744 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 197056 KB Output is correct
2 Correct 917 ms 193500 KB Output is correct
3 Correct 695 ms 181024 KB Output is correct
4 Correct 720 ms 183348 KB Output is correct
5 Execution timed out 3513 ms 179628 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 187300 KB Output is correct
2 Correct 592 ms 187180 KB Output is correct
3 Correct 440 ms 172596 KB Output is correct
4 Correct 490 ms 172732 KB Output is correct
5 Correct 430 ms 172584 KB Output is correct
6 Correct 544 ms 174544 KB Output is correct
7 Correct 582 ms 174700 KB Output is correct
8 Correct 590 ms 174696 KB Output is correct
9 Correct 562 ms 175136 KB Output is correct
10 Correct 533 ms 175132 KB Output is correct
11 Correct 438 ms 175024 KB Output is correct
12 Correct 445 ms 175004 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 510 ms 286404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 502 ms 286668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -