oj.uz

Submission #140312

# Submission time Handle Problem Language Result Execution time Memory
140312 2019-08-02T14:03:42 Z FedericoS Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 4984 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;

int N;
int x,y,z;
vector<pii> grafo[200005];
int A[200005],B[200005];

void DFS(int k, int p=-1){

	for(pii f:grafo[k])
		if(f.first!=p)
			DFS(f.first,k);

	vector<int> v;
	for(pii f:grafo[k])
		if(f.first!=p){
			A[k]+=max(A[f.first],B[f.first]+f.second);
			v.push_back(A[f.first]+f.second-max(A[f.first],B[f.first]+f.second));
		}
	sort(v.begin(),v.end(),greater<int>());

	if(grafo[k].size()==1 and k!=1)
		B[k]=-2e9;
	else
		B[k]=A[k]+v[0];
	if(v.size()>1 and v[0]+v[1]>0)
		A[k]=A[k]+v[0]+v[1];

}

int main(){
	cin>>N;
	for(int i=0;i<N-1;i++){
		cin>>x>>y>>z;
		grafo[x].push_back({y,z});
		grafo[y].push_back({x,z});
	}

	DFS(1);
	cout<<A[1];

}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Halted 0 ms 0 KB -