oj.uz

Submission #883834

# Submission time Handle Problem Language Result Execution time Memory
883834 2023-12-06T07:41:28 Z vjudge1 Putovanje (COCI20_putovanje) C++17
45 / 110
 1000 ms 70280 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);
  for (auto it : edges[node]) {
    if (it == p) continue;
    for (auto itt : sts[it]) {
      int c = 2;
      c-=(itt==1 || anc(it,itt-1));
      c-=(itt==n || anc(it,itt+1));
      pass[edg[it]]+=c;
    }
  }
  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]) 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:83:10: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |     yeter(root,root,0);
      |     ~~~~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26972 KB Output is correct
2 Correct 10 ms 27484 KB Output is correct
3 Correct 10 ms 27740 KB Output is correct
4 Correct 10 ms 27740 KB Output is correct
5 Correct 10 ms 27740 KB Output is correct
6 Correct 7 ms 26972 KB Output is correct
7 Correct 9 ms 27140 KB Output is correct
8 Correct 11 ms 27560 KB Output is correct
9 Correct 10 ms 27700 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 52200 KB Output is correct
2 Correct 183 ms 54012 KB Output is correct
3 Correct 168 ms 56916 KB Output is correct
4 Correct 164 ms 57940 KB Output is correct
5 Correct 8 ms 27224 KB Output is correct
6 Correct 128 ms 53076 KB Output is correct
7 Correct 90 ms 45648 KB Output is correct
8 Correct 159 ms 54476 KB Output is correct
9 Correct 104 ms 56660 KB Output is correct
10 Correct 107 ms 55832 KB Output is correct
11 Correct 102 ms 58108 KB Output is correct
12 Correct 98 ms 58332 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26972 KB Output is correct
2 Correct 10 ms 27484 KB Output is correct
3 Correct 10 ms 27740 KB Output is correct
4 Correct 10 ms 27740 KB Output is correct
5 Correct 10 ms 27740 KB Output is correct
6 Correct 7 ms 26972 KB Output is correct
7 Correct 9 ms 27140 KB Output is correct
8 Correct 11 ms 27560 KB Output is correct
9 Correct 10 ms 27700 KB Output is correct
10 Correct 129 ms 52200 KB Output is correct
11 Correct 183 ms 54012 KB Output is correct
12 Correct 168 ms 56916 KB Output is correct
13 Correct 164 ms 57940 KB Output is correct
14 Correct 8 ms 27224 KB Output is correct
15 Correct 128 ms 53076 KB Output is correct
16 Correct 90 ms 45648 KB Output is correct
17 Correct 159 ms 54476 KB Output is correct
18 Correct 104 ms 56660 KB Output is correct
19 Correct 107 ms 55832 KB Output is correct
20 Correct 102 ms 58108 KB Output is correct
21 Correct 98 ms 58332 KB Output is correct
22 Correct 349 ms 70280 KB Output is correct
23 Correct 263 ms 65692 KB Output is correct
24 Correct 335 ms 69816 KB Output is correct
25 Correct 9 ms 27228 KB Output is correct
26 Correct 111 ms 45908 KB Output is correct
27 Correct 227 ms 62988 KB Output is correct
28 Execution timed out 1059 ms 50328 KB Time limit exceeded
29 Halted 0 ms 0 KB -