oj.uz

Submission #738468

# Submission time Handle Problem Language Result Execution time Memory
738468 2023-05-08T19:58:00 Z Sam_a17 Putovanje (COCI20_putovanje) C++17
110 / 110
 152 ms 28796 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};

int ka() {
	int x = 0;
	bool z = false;
	while (1)
	{
		char y = getchar();
		if (y == '-')
			z = true;
		else if ('0' <= y && y <= '9')
			x = x * 10 + y - '0';
		else
		{
			if (z)
				x *= -1;
			return x;
		}
	}
}

// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10, LOG = 23;
long long n, c1[N], c2[N];
vector<pair<int, int>> adj[N];

int sz[N];

int up[N][LOG], depths[N], p[N];

void dfs(int node, int parent, int depth) {
  p[node] = parent;
  sz[node] = 1;
  depths[node] = depths[parent] + 1;
  for(auto i: adj[node]) {
    if(i.first == parent) continue;
    up[i.first][0] = node;
    for(int j = 1; j < LOG; j++) {
      up[i.first][j] = up[up[i.first][j - 1]][j - 1];
    } 
    dfs(i.first, node, depth + 1);
    sz[node] += sz[i.first];
  }
}

int lca(int a, int b) {
  if(a == b) {
    return a;
  }

  if(depths[a] > depths[b]) {
    swap(a, b);
  }

  int delta = depths[b] - depths[a];
  for(int i = 0; i < LOG; i++) {
    if(delta & (1 << i)) {
      b = up[b][i];
    }
  }

  if(a == b) {
    return a;
  }

  for(int i = LOG - 1; i >= 0; i--) {
    if(up[a][i] != up[b][i]) {
      a = up[a][i], b = up[b][i];
    }
  }
  return up[a][0];
}

long long q[N];
long long answ = 0;

void dfs1(int node, int parent) {
  for(auto i: adj[node]) {
    if(i.first == parent) continue;
    dfs1(i.first, node);

    long long cc = c1[i.second] * q[i.first];
    answ += min(cc, c2[i.second]);
    q[node] += q[i.first];
  }
}



void solve_() {
  cin >> n;

  for(int i = 1; i <= n - 1; i++) {
    int a, b; cin >> a >> b;
    cin >> c1[i] >> c2[i];
    adj[a].push_back({b, i});
    adj[b].push_back({a, i});
  }

  dfs(1, 0, 0);


  for(int i = 2; i <= n; i++) {
    q[i]++, q[i - 1]++;
    q[lca(i, i - 1)] -= 2;
  }

  dfs1(1, 0);

  cout << answ << '\n';
}
 
int main() {
  setIO();

  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

putovanje.cpp: In function 'void setIO(std::string)':
putovanje.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:84:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5332 KB Output is correct
3 Correct 4 ms 5296 KB Output is correct
4 Correct 5 ms 5460 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 3 ms 5044 KB Output is correct
8 Correct 3 ms 5304 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 24900 KB Output is correct
2 Correct 120 ms 26112 KB Output is correct
3 Correct 126 ms 28796 KB Output is correct
4 Correct 152 ms 28236 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 125 ms 24368 KB Output is correct
7 Correct 74 ms 19276 KB Output is correct
8 Correct 135 ms 24976 KB Output is correct
9 Correct 69 ms 25788 KB Output is correct
10 Correct 65 ms 25164 KB Output is correct
11 Correct 71 ms 26828 KB Output is correct
12 Correct 70 ms 27084 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5332 KB Output is correct
3 Correct 4 ms 5296 KB Output is correct
4 Correct 5 ms 5460 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 3 ms 5044 KB Output is correct
8 Correct 3 ms 5304 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 125 ms 24900 KB Output is correct
11 Correct 120 ms 26112 KB Output is correct
12 Correct 126 ms 28796 KB Output is correct
13 Correct 152 ms 28236 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 125 ms 24368 KB Output is correct
16 Correct 74 ms 19276 KB Output is correct
17 Correct 135 ms 24976 KB Output is correct
18 Correct 69 ms 25788 KB Output is correct
19 Correct 65 ms 25164 KB Output is correct
20 Correct 71 ms 26828 KB Output is correct
21 Correct 70 ms 27084 KB Output is correct
22 Correct 103 ms 22852 KB Output is correct
23 Correct 84 ms 20660 KB Output is correct
24 Correct 97 ms 22420 KB Output is correct
25 Correct 4 ms 5204 KB Output is correct
26 Correct 36 ms 12900 KB Output is correct
27 Correct 78 ms 19996 KB Output is correct
28 Correct 66 ms 23244 KB Output is correct
29 Correct 71 ms 27084 KB Output is correct
30 Correct 79 ms 26656 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct