oj.uz

Submission #868181

# Submission time Handle Problem Language Result Execution time Memory
868181 2023-10-30T16:27:34 Z amirhoseinfar1385 Magic Tree (CEOI19_magictree) C++17
68 / 100
 2000 ms 28240 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
vector<int>adj[maxn];
int n,m,k;
pair<int,int>allq[maxn];
set<pair<int,int>>st[maxn];

void insert(int u){
	if(allq[u].second==0){
		return ;
	}
	auto x=allq[u];
	pair<int,int>y;
	if((int)st[u].size()>0&&(*st[u].rbegin()).first>=x.first){
		y=*st[u].lower_bound(make_pair(x.first,-1));
	}
	else{
		y.first=-1;
	}
	if(y.first==x.first){
		x.second+=y.second;
		st[u].erase(y);
	}
	st[u].insert(x);
	int z=x.first;
	while((int)st[u].size()>0&&(*st[u].rbegin()).first>z){
		y=*st[u].lower_bound(make_pair(z+1,-1));
		if(y.second<allq[u].second){
			st[u].erase(y);
			allq[u].second-=y.second;
		}	
		else{
			st[u].erase(y);
			y.second-=allq[u].second;
			st[u].insert(y);
			allq[u].second=0;
			break;
		}
	}
}

void merge(int u,int v){
	int fu=u,fv=v;
	if((int)st[u].size()<(int)st[v].size()){
		swap(u,v);
	}
	for(auto x:st[v]){
		auto y=*st[u].lower_bound(make_pair(x.first,-1));
		if((int)st[u].size()==0||(*st[u].rbegin()).first<x.first||y.first!=x.first){
			st[u].insert(x);
		}
		else{
			st[u].erase(y);
			y.second+=x.second;
			st[u].insert(y);
		}
	}
	if(u!=fu){
		swap(st[u],st[fu]);
	}
}

/*void co(int u){
	cout<<"u: "<<u<<" \n";
	for(auto x:st[u]){
		cout<<x.first<<" "<<x.second<<"\n";
	}
}*/

void solve(int u=1){
	if((int)adj[u].size()==0){
		insert(u);
		//co(u);
		return ;
	}
	solve(adj[u][0]);
	swap(st[u],st[adj[u][0]]);
	for(int i=1;i<(int)adj[u].size();i++){
		solve(adj[u][i]);
		merge(u,adj[u][i]);
	}
	insert(u);
	//co(u);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		int d;
		cin>>d;
		adj[d].push_back(i);
	}
	for(int i=0;i<m;i++){
		int v,d,w;
		cin>>v>>d>>w;
		allq[v]=make_pair(d,w);
	}
	solve();
	long long res=0;
	for(auto x:st[1]){
		res+=x.second;
	}
	cout<<res<<'\n';
}

Compilation message

magictree.cpp: In function 'void merge(int, int)':
magictree.cpp:44:11: warning: unused variable 'fv' [-Wunused-variable]
   44 |  int fu=u,fv=v;
      |           ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 2 ms 8140 KB Output is correct
6 Correct 2 ms 8280 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 15348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 58 ms 17656 KB Output is correct
5 Correct 48 ms 20564 KB Output is correct
6 Correct 81 ms 17496 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2032 ms 9816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 2 ms 8140 KB Output is correct
6 Correct 2 ms 8280 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 73 ms 15696 KB Output is correct
11 Correct 56 ms 14928 KB Output is correct
12 Correct 45 ms 14108 KB Output is correct
13 Correct 33 ms 12760 KB Output is correct
14 Correct 46 ms 17500 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 21 ms 10012 KB Output is correct
3 Correct 15 ms 9820 KB Output is correct
4 Correct 16 ms 9908 KB Output is correct
5 Correct 7 ms 8940 KB Output is correct
6 Correct 15 ms 10840 KB Output is correct
7 Correct 17 ms 13144 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 2 ms 8140 KB Output is correct
6 Correct 2 ms 8280 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 2 ms 8280 KB Output is correct
12 Correct 2 ms 8284 KB Output is correct
13 Correct 58 ms 17656 KB Output is correct
14 Correct 48 ms 20564 KB Output is correct
15 Correct 81 ms 17496 KB Output is correct
16 Correct 73 ms 15696 KB Output is correct
17 Correct 56 ms 14928 KB Output is correct
18 Correct 45 ms 14108 KB Output is correct
19 Correct 33 ms 12760 KB Output is correct
20 Correct 46 ms 17500 KB Output is correct
21 Correct 20 ms 11096 KB Output is correct
22 Correct 66 ms 16980 KB Output is correct
23 Correct 70 ms 20148 KB Output is correct
24 Correct 120 ms 28240 KB Output is correct
25 Correct 64 ms 15456 KB Output is correct
26 Correct 105 ms 16888 KB Output is correct
27 Correct 95 ms 15696 KB Output is correct

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 2 ms 8140 KB Output is correct
6 Correct 2 ms 8280 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Incorrect 46 ms 15348 KB Output isn't correct
11 Halted 0 ms 0 KB -