oj.uz

Submission #868180

# Submission time Handle Problem Language Result Execution time Memory
868180 2023-10-30T16:26:47 Z amirhoseinfar1385 Magic Tree (CEOI19_magictree) C++17
27 / 100
 2000 ms 32336 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15708 KB Output is correct
2 Correct 30 ms 16464 KB Output is correct
3 Correct 117 ms 32336 KB Output is correct
4 Correct 66 ms 19156 KB Output is correct
5 Correct 73 ms 20304 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 47 ms 17656 KB Output is correct
5 Correct 47 ms 20564 KB Output is correct
6 Correct 80 ms 17548 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 20 ms 9928 KB Output is correct
3 Correct 19 ms 9820 KB Output is correct
4 Correct 16 ms 10076 KB Output is correct
5 Correct 7 ms 8928 KB Output is correct
6 Correct 21 ms 11116 KB Output is correct
7 Correct 15 ms 13144 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8284 KB Output isn't correct
4 Halted 0 ms 0 KB -