oj.uz

답안 #350013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
350013 2021-01-18T21:08:09 Z arnold518 Putovanje (COCI20_putovanje) C++14
110 / 110
 213 ms 30460 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

struct Edge
{
	int u, v, p, q;
};

int N;
vector<Edge> adj[MAXN+10];

int par[MAXN+10][30], dep[MAXN+10];
int dp[MAXN+10];

void dfs(int now, int bef, int d)
{
	par[now][0]=bef;
	dep[now]=d;
	for(auto nxt : adj[now])
	{
		if(nxt.v==bef) continue;
		dfs(nxt.v, now, d+1);
	}
}

int lca(int u, int v)
{
	if(dep[u]>dep[v]) swap(u, v);
	for(int i=20; i>=0; i--) if(dep[u]<=dep[par[v][i]]) v=par[v][i];
	if(u==v) return u;
	for(int i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
	return par[u][0];
}

ll ans;
void dfs2(int now, int bef, int p, int q)
{
	for(auto nxt : adj[now])
	{
		if(nxt.v==bef) continue;
		dfs2(nxt.v, now, nxt.p, nxt.q);
		dp[now]+=dp[nxt.v];
	}
	ans+=min((ll)dp[now]*p, (ll)q);
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<N; i++)
	{
		int u, v, p, q;
		scanf("%d%d%d%d", &u, &v, &p, &q);
		adj[u].push_back({u, v, p, q});
		adj[v].push_back({v, u, p, q});
	}

	dfs(1, 0, 1);
	for(int i=1; i<=20; i++) for(int j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

	for(int i=1; i<N; i++)
	{
		int u=i, v=i+1, w=lca(u, v);
		dp[u]++; dp[v]++;
		dp[w]--; dp[w]--;
	}

	dfs2(1, 0, 0, 0);
	printf("%lld\n", ans);
}

Compilation message

putovanje.cpp: In function 'int main()':
putovanje.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
putovanje.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d%d%d%d", &u, &v, &p, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 5 ms 5356 KB Output is correct
3 Correct 5 ms 5356 KB Output is correct
4 Correct 5 ms 5484 KB Output is correct
5 Correct 6 ms 5484 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 5 ms 5228 KB Output is correct
9 Correct 5 ms 5356 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 26220 KB Output is correct
2 Correct 177 ms 27628 KB Output is correct
3 Correct 188 ms 30460 KB Output is correct
4 Correct 213 ms 29932 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 162 ms 25708 KB Output is correct
7 Correct 93 ms 20204 KB Output is correct
8 Correct 182 ms 26348 KB Output is correct
9 Correct 105 ms 27372 KB Output is correct
10 Correct 103 ms 26732 KB Output is correct
11 Correct 118 ms 28652 KB Output is correct
12 Correct 115 ms 28652 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 5 ms 5356 KB Output is correct
3 Correct 5 ms 5356 KB Output is correct
4 Correct 5 ms 5484 KB Output is correct
5 Correct 6 ms 5484 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 5 ms 5228 KB Output is correct
9 Correct 5 ms 5356 KB Output is correct
10 Correct 175 ms 26220 KB Output is correct
11 Correct 177 ms 27628 KB Output is correct
12 Correct 188 ms 30460 KB Output is correct
13 Correct 213 ms 29932 KB Output is correct
14 Correct 4 ms 5228 KB Output is correct
15 Correct 162 ms 25708 KB Output is correct
16 Correct 93 ms 20204 KB Output is correct
17 Correct 182 ms 26348 KB Output is correct
18 Correct 105 ms 27372 KB Output is correct
19 Correct 103 ms 26732 KB Output is correct
20 Correct 118 ms 28652 KB Output is correct
21 Correct 115 ms 28652 KB Output is correct
22 Correct 145 ms 24172 KB Output is correct
23 Correct 124 ms 21868 KB Output is correct
24 Correct 143 ms 23788 KB Output is correct
25 Correct 4 ms 5228 KB Output is correct
26 Correct 51 ms 13548 KB Output is correct
27 Correct 112 ms 21228 KB Output is correct
28 Correct 96 ms 24684 KB Output is correct
29 Correct 114 ms 28652 KB Output is correct
30 Correct 110 ms 28268 KB Output is correct
31 Correct 5 ms 5356 KB Output is correct