oj.uz

답안 #957605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957605 2024-04-04T05:13:05 Z vjudge1 Putovanje (COCI20_putovanje) C++17
20 / 110
 91 ms 37456 KB 
#include <bits/stdc++.h>
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define fast_io ios::sync_with_stdio(false);cin.tie(0);
#define what(x) cerr << #x << " is " << x << '\n';
#define kill(x) {cout << x << '\n'; return;}
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define pb push_back
#define ll long long
#define F first
#define S second
const ll inf = 1e16, mod = 1e9 + 7, delta = 1e9 + 9, SQ = 350, P = 6065621;

using namespace std;

const int N = 2e5 + 10, LG = 21;
int c1[N], c2[N], par[N][LG], yalp[N], h[N], cnt[N], a[N];
vector<pii> adj[N];

void dfs (int v, int p = -1) {
  par[v][0] = p;
  if (v == 1) yalp[v] = -1;
  if (p + 1) h[v] = h[p] + 1;
  for (int i = 1; i < LG; i++)
    if (par[v][i - 1] + 1)
      par[v][i] = par[par[v][i - 1]][i - 1];
  for (auto [u, _]: adj[v])
    if (u - p) dfs(u, v), yalp[u] = _;
}

int lca (int v, int u) {
  if (h[u] < h[v]) swap(u, v);
  for (int i = LG - 1; i >= 0; i--)
    if (par[u][i] + 1 && h[par[u][i]] >= h[v])
      u = par[u][i];
  if (u == v) return v;
  for (int i = LG - 1; i >= 0; i--)
    if (par[v][i] != par[u][i])
      v = par[v][i], u = par[u][i];
  return par[v][0];
}

void diefes (int v, int p = -1) {
  for (auto u: adj[v]) {
    if (u.F - p) {
      diefes(u.F, v);
      cnt[u.S] = a[u.F];
      a[v] += a[u.F];
    }
  }
}

int main () {
  fast_io;
  int n;
  cin >> n;
  memset(par, -1, sizeof par);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v >> c1[i] >> c2[i];
    adj[u].pb({v, i});
    adj[v].pb({u, i});
  }
  dfs(1);
  int cur = 1; 
  for (int i = 2; i <= n; i++) {
    if (i == cur) continue;
    int l = lca(i, cur);
    if (l == i) {
      a[cur]++;
      a[i]--;
    } 
    else if (l == cur) {
      a[i]++;
      a[cur]--;
    }
    else {
      a[i]++;
      a[cur]++;
      a[l] -= 2;
    }
    cur = i;
  }
  diefes(1);
  ll ans = 0;
  for (int i = 1; i < n; i++) 
    ans += min(c2[i], c1[i] * cnt[i]);
  cout << ans << '\n'; 
  return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 25180 KB Output is correct
2 Correct 5 ms 25180 KB Output is correct
3 Correct 5 ms 25180 KB Output is correct
4 Correct 5 ms 25188 KB Output is correct
5 Correct 5 ms 25180 KB Output is correct
6 Correct 4 ms 25180 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 5 ms 25236 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 34388 KB Output is correct
2 Correct 85 ms 35664 KB Output is correct
3 Incorrect 91 ms 37456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 25180 KB Output is correct
2 Correct 5 ms 25180 KB Output is correct
3 Correct 5 ms 25180 KB Output is correct
4 Correct 5 ms 25188 KB Output is correct
5 Correct 5 ms 25180 KB Output is correct
6 Correct 4 ms 25180 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 5 ms 25236 KB Output is correct
10 Correct 80 ms 34388 KB Output is correct
11 Correct 85 ms 35664 KB Output is correct
12 Incorrect 91 ms 37456 KB Output isn't correct
13 Halted 0 ms 0 KB -