oj.uz

답안 #883865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883865 2023-12-06T08:38:37 Z vjudge1 Putovanje (COCI20_putovanje) C++17
25 / 110
 172 ms 57424 KB 
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 2e5+1;
int t = 1;
vi edges[N],v(N),w(N),pass(N,0),tin(N),tout(N),edg(N),pp(N),lazy(N,0);
set<int> sts[N];
map<pii,int> edgs;
int n;
void gg(int node,int p) {
  edg[node] = edgs[{node,p}];
  tin[node] = t++;
  for (auto it : edges[node]) if (it != p) gg(it,node);
  tout[node] = t++;
}
bool anc(int a,int b) {
  return (tin[a] <= tin[b]) && (tout[a] >= tout[b]);
}
void dfs(int node,int p) {
  for (auto it : edges[node]) if (it != p) dfs(it,node);
  sts[node].insert(node);
  for (auto it : edges[node]) {
    if (it == p) continue;
    if (sts[it].size() > sts[node].size()) sts[node].swap(sts[it]);
    for (auto itt : sts[it]) {
      int c = 2;
      c-=(itt==1 || anc(it,itt-1));
      c-=(itt==n || anc(it,itt+1));
      pass[edgs[{it,node}]]+=c;
    }
    for (auto itt : sts[it]) sts[node].insert(itt);
  }
}

void dfsss(int node,int p) {
  pp[node] = t++;
  for (auto it : edges[node]) if (it != p) dfsss(it,node);
} 
void yeter(int node,int p,int cur) {
  cur+=lazy[node];
  for (auto it : edges[node]) {
    if (it != p) {
      pass[edgs[{node,it}]]+=cur;
      yeter(it,node,cur);
    }
  }
}
void solve() {
  cin >> n;
  vi ss(n+1,0);
  F(i,n-1) {
    int a,b;
    cin >> a >> b >> v[i] >> w[i];
    edges[a].push_back(b);
    edges[b].push_back(a);
    ss[a]++;
    ss[b]++;
    edgs[{a,b}] = edgs[{b,a}] = i;
  }
  if (*max_element(ss.begin(),ss.end()) <= 2){
    int root;
    for (int i=1;i<=n;i++) {
      if (ss[i] == 1) root = i;
    }
    dfsss(root,root);
    for (int i=2;i<=n;i++){
      if (pp[i] < pp[i-1]) {
        lazy[i]++;
        lazy[i-1]--;
      }
      else {
        lazy[i-1]++;
        lazy[i]--;
      }
    }
    yeter(root,root,0);
  }
  else {
    gg(1,1);
    dfs(1,1);
  }
  int ans = 0;
  F(i,n-1) {
    if (pass[i]*v[i] <= w[i]) ans+=pass[i]*v[i];
    else ans+=w[i];
  }
  cout << ans << endl;
}
    
                  
                             
signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #ifdef Local
  freopen("in","r",stdin);
  freopen("out","w",stdout); 
  #endif
  int t = 1;
  //cin >> t;
	F(i,t) solve();
}

Compilation message

putovanje.cpp: In function 'void solve()':
putovanje.cpp:80:10: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |     yeter(root,root,0);
      |     ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 26972 KB Output is correct
2 Incorrect 11 ms 27740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 53448 KB Output is correct
2 Correct 146 ms 53840 KB Output is correct
3 Correct 172 ms 56160 KB Output is correct
4 Correct 171 ms 57420 KB Output is correct
5 Correct 9 ms 27224 KB Output is correct
6 Correct 136 ms 52832 KB Output is correct
7 Correct 105 ms 45224 KB Output is correct
8 Correct 146 ms 53800 KB Output is correct
9 Correct 94 ms 55824 KB Output is correct
10 Correct 88 ms 55124 KB Output is correct
11 Correct 100 ms 57296 KB Output is correct
12 Correct 97 ms 57424 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 26972 KB Output is correct
2 Incorrect 11 ms 27740 KB Output isn't correct
3 Halted 0 ms 0 KB -