oj.uz

Submission #463494

# Submission time Handle Problem Language Result Execution time Memory
463494 2021-08-11T09:03:30 Z Jasiekstrz Putovanje (COCI20_putovanje) C++17
110 / 110
 228 ms 28396 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int L=20;
const int PP=3e5;
int pot;
int tree[2*PP+10];
vector<pair<int,int>> e[N+10];
long long c[N+10][2];
int pre[N+10];
int post[N+10];
int d[N+10];
int jmp[N+10][L+2];
void dfs_pre(int x,int p)
{
	static int nr=0;
	pre[x]=++nr;
	d[x]=d[p]+1;
	jmp[x][0]=p;
	for(int l=1;l<=L;l++)
		jmp[x][l]=jmp[jmp[x][l-1]][l-1];
	for(auto [v,id]:e[x])
	{
		if(v==p)
			continue;
		dfs_pre(v,x);
	}
	post[x]=nr;
	return;
}
int lca(int x,int y)
{
	if(d[x]>d[y])
		swap(x,y);
	for(int l=L;l>=0;l--)
	{
		if(d[jmp[y][l]]>=d[x])
			y=jmp[y][l];
	}
	if(x==y)
		return x;
	for(int l=L;l>=0;l--)
	{
		if(jmp[x][l]!=jmp[y][l])
		{
			x=jmp[x][l];
			y=jmp[y][l];
		}
	}
	return jmp[x][0];
}
void add(int x,int cc)
{
	for(x+=pot-1;x>0;x/=2)
		tree[x]+=cc;
	return;
}
int read(int l,int r)
{
	int ans=0;
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ans+=tree[l++];
		if(r%2==0)
			ans+=tree[r--];
	}
	return ans;
}
long long dfs_ans(int x,int p)
{
	long long ans=0;
	for(auto [v,id]:e[x])
	{
		if(v==p)
			continue;
		ans+=dfs_ans(v,x);
		ans+=min(c[id][1],c[id][0]*read(pre[v],post[v]));
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b>>c[i][0]>>c[i][1];
		e[a].emplace_back(b,i);
		e[b].emplace_back(a,i);
	}
	dfs_pre(1,0);
	for(int i=1;i<n;i++)
	{
		add(pre[i],1);
		add(pre[i+1],1);
		add(pre[lca(i,i+1)],-2);
	}
	cout<<dfs_ans(1,0)<<"\n";
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 5324 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 5 ms 5288 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5184 KB Output is correct
9 Correct 5 ms 5264 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 24472 KB Output is correct
2 Correct 228 ms 25832 KB Output is correct
3 Correct 218 ms 28396 KB Output is correct
4 Correct 222 ms 27988 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 207 ms 24068 KB Output is correct
7 Correct 121 ms 19044 KB Output is correct
8 Correct 214 ms 24488 KB Output is correct
9 Correct 117 ms 25480 KB Output is correct
10 Correct 115 ms 24860 KB Output is correct
11 Correct 127 ms 26500 KB Output is correct
12 Correct 125 ms 26716 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 5324 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 5 ms 5288 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5184 KB Output is correct
9 Correct 5 ms 5264 KB Output is correct
10 Correct 198 ms 24472 KB Output is correct
11 Correct 228 ms 25832 KB Output is correct
12 Correct 218 ms 28396 KB Output is correct
13 Correct 222 ms 27988 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 207 ms 24068 KB Output is correct
16 Correct 121 ms 19044 KB Output is correct
17 Correct 214 ms 24488 KB Output is correct
18 Correct 117 ms 25480 KB Output is correct
19 Correct 115 ms 24860 KB Output is correct
20 Correct 127 ms 26500 KB Output is correct
21 Correct 125 ms 26716 KB Output is correct
22 Correct 175 ms 22536 KB Output is correct
23 Correct 165 ms 20244 KB Output is correct
24 Correct 190 ms 22100 KB Output is correct
25 Correct 4 ms 5196 KB Output is correct
26 Correct 60 ms 12748 KB Output is correct
27 Correct 131 ms 19856 KB Output is correct
28 Correct 100 ms 22908 KB Output is correct
29 Correct 129 ms 26640 KB Output is correct
30 Correct 122 ms 26272 KB Output is correct
31 Correct 5 ms 5324 KB Output is correct