oj.uz

Submission #202078

# Submission time Handle Problem Language Result Execution time Memory
202078 2020-02-13T14:36:04 Z Milki Putovanje (COCI20_putovanje) C++14
0 / 110
 196 ms 23768 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

const int MAXN = 2e5 + 5, LOG = 19;

struct Edge{
  int x = -1, cost1 = -1, cost2 = -1;
  Edge(){}
  Edge(int x, int cost1, int cost2) : x(x), cost1(cost1), cost2(cost2) {}
};

int n, anc[LOG][MAXN], dep[MAXN];
vector <Edge> E[MAXN];
Edge par[MAXN];

void dfs(int x, int p = -1){
  for(auto e : E[x]){
    if(e.x == p) continue;
    dep[e.x] = dep[x] + 1;
    anc[0][e.x] = x;
    par[e.x] = e;
    dfs(e.x, x);
  }
}

int get_lca(int x, int y){
  if(dep[x] < dep[y])
    swap(x, y);

  for(int i = LOG - 1; i >= 0; --i)
    if( dep[x] - (1 << i) >= dep[y] )
      x = anc[i][x];

  if(x == y) return x;
  for(int i = LOG - 1; i >= 0; --i)
    if( anc[i][x] != anc[i][y] ){
      x = anc[i][x];
      y = anc[i][y];
    }
  return anc[0][x];
}

ll extra[MAXN], sum[MAXN];

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n;
  REP(i, n - 1){
    int a, b, cost1, cost2; cin >> a >> b >> cost1 >> cost2;
    a --; b --;
    E[a].pb(Edge(b, cost1, cost2));
    E[b].pb(Edge(a, cost1, cost2));
  }
  dfs(0);

  FOR(i, 1, LOG) REP(j, n){
    int x = anc[i - 1][j];
    anc[i][j] = anc[i - 1][x];
  }

  FOR(i, 1, n){
    int x = i, y = i - 1;
    if(dep[x] > dep[y])
      swap(x, y);
    int lca = get_lca(x, y);

    if(lca != x && lca != y){
      extra[x] ++; extra[y] ++;
      extra[lca] --;
      if(lca != 0)
        extra[anc[0][lca]] --;
    }
    else if(lca == x){
      extra[y] ++;
      if(lca != 0)
        extra[anc[0][lca]] --;
    }
    else
      assert(n == 0);
  }

  vector <point> v;
  REP(i, n)
    v.pb(point( dep[i], i ));
  sort(v.rbegin(), v.rend());

  ll sol = 0;
  for(auto it : v){
    int x = it.second;
    if(x != 0){
      extra[anc[0][x]] += extra[x];
      ll add1 = (ll)par[x].cost1 * (ll)extra[x];
      ll add2 = (ll)par[x].cost2;
      sol += min(add1, add2);
    }
  }
  cout << sol;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7520 KB Output is correct
2 Incorrect 11 ms 7776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 21492 KB Output is correct
2 Correct 161 ms 22336 KB Output is correct
3 Correct 180 ms 23768 KB Output is correct
4 Correct 196 ms 23664 KB Output is correct
5 Correct 11 ms 7544 KB Output is correct
6 Correct 159 ms 21204 KB Output is correct
7 Incorrect 99 ms 17500 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7520 KB Output is correct
2 Incorrect 11 ms 7776 KB Output isn't correct
3 Halted 0 ms 0 KB -