oj.uz

Submission #522195

# Submission time Handle Problem Language Result Execution time Memory
522195 2022-02-04T03:56:27 Z Killer2501 Putovanje (COCI20_putovanje) C++14
110 / 110
 149 ms 30128 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
using namespace std;
const int N = 3e5+5;
const int M = 350;
const ll mod = 1e9+9;
const ll inf = 2e9;
int m, k, t,  n;
ll ans;
int a[N], b[N], c[N][2], h[N], d[N], P[N][20];
string s;
vector<int> adj[N], kq;
vector<int> val;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
ll pw(ll k, ll n)
{
    ll total =1 ;
    for(; n; n >>= 1)
    {
        if(n&1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
struct node
{
	int l, r, val, lazy;
    node(){}
    node(int _l, int _r, int _val, int _lazy)
    {
    	l = _l;
    	r = _r;
    	val = _val;
    	lazy = _lazy;
    }
};
vector<node> st;
int build(int l, int r)
{
	if(l == r)
	{
		st.pb(node(0, 0, b[l], 0));
		return st.size()-1;
	}
	int mid = (l+r)>>1;
	node cur;
	cur.l = build(l, mid);
	cur.r = build(mid+1, r);
	cur.lazy = 0;
	cur.val = min(st[cur.l].val, st[cur.r].val);
	st.pb(cur);
	return st.size()-1;
}
struct BIT
{
	int n;
	vector<int> fe;
	BIT(int _n)
	{
		n = _n;
		fe.resize(n+1, 0);
	}
	void add(int id, int x)
	{
		for(; id <= n; id += id & -id)fe[id] += x;
	}
	void add(int l, int r, int x)
	{
		if(l > r)swap(l, r);
		add(l, x);
		add(r, -x);
	}
	int get(int id)
	{
		int total = 0;
		for(; id; id -= id & -id)total += fe[id];
		return total;
	}
};
void dfs(int u, int p = 0)
{
	for(int i: adj[u])
	{
		int v = a[i]^b[i]^u;
		if(v == p)continue;
		h[v] = h[u]+1;
		P[v][0] = u;
		for(int i = 1; i < 19; i ++)P[v][i] = P[P[v][i-1]][i-1];
		dfs(v, u);

	}
}
int lca(int u, int v)
{
	if(h[u] < h[v])swap(u, v);
	int log = log2(h[u]);
	for(int i = log; i >= 0; i --)if(h[u] >= h[v]+(1<<i))u = P[u][i];
	if(u == v)return u;
	for(int i = log; i >= 0; i --)
	{
		if(P[u][i] && P[v][i] != P[u][i])
		{
			u = P[u][i];
			v = P[v][i];
		}
	}
	return P[u][0];
}
void cal(int u, int p = 0)
{
	for(int i: adj[u])
	{
		int v = a[i]^b[i]^u;
		if(v == p)continue;
		cal(v, u);
		d[u] += d[v];
		ans += min(c[i][1]*1ll, 1ll*d[v]*c[i][0]);
	}
}
void sol(int icase)
{
	cin >> n;
	for(int i = 1; i < n; i ++)
	{
		cin >> a[i] >> b[i] >> c[i][0] >> c[i][1];
		adj[a[i]].pb(i);
		adj[b[i]].pb(i);
	}
	dfs(1);
	for(int i = 1; i < n; i ++)
	{
		k = lca(i, i+1);
		++d[i];
		++d[i+1];
		d[k] -= 2;
	}
	cal(1);
	cout << ans;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    for(int i = 1; i <= test; i ++)sol(i);
    return 0;
}

Compilation message

putovanje.cpp: In function 'int main()':
putovanje.cpp:155:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:156:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7364 KB Output is correct
2 Correct 6 ms 7620 KB Output is correct
3 Correct 5 ms 7640 KB Output is correct
4 Correct 8 ms 7628 KB Output is correct
5 Correct 7 ms 7644 KB Output is correct
6 Correct 4 ms 7308 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7628 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 26032 KB Output is correct
2 Correct 149 ms 27584 KB Output is correct
3 Correct 126 ms 30128 KB Output is correct
4 Correct 138 ms 29364 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 137 ms 25580 KB Output is correct
7 Correct 65 ms 20944 KB Output is correct
8 Correct 149 ms 25972 KB Output is correct
9 Correct 71 ms 26572 KB Output is correct
10 Correct 62 ms 26032 KB Output is correct
11 Correct 72 ms 27652 KB Output is correct
12 Correct 72 ms 27972 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7364 KB Output is correct
2 Correct 6 ms 7620 KB Output is correct
3 Correct 5 ms 7640 KB Output is correct
4 Correct 8 ms 7628 KB Output is correct
5 Correct 7 ms 7644 KB Output is correct
6 Correct 4 ms 7308 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7628 KB Output is correct
10 Correct 115 ms 26032 KB Output is correct
11 Correct 149 ms 27584 KB Output is correct
12 Correct 126 ms 30128 KB Output is correct
13 Correct 138 ms 29364 KB Output is correct
14 Correct 4 ms 7500 KB Output is correct
15 Correct 137 ms 25580 KB Output is correct
16 Correct 65 ms 20944 KB Output is correct
17 Correct 149 ms 25972 KB Output is correct
18 Correct 71 ms 26572 KB Output is correct
19 Correct 62 ms 26032 KB Output is correct
20 Correct 72 ms 27652 KB Output is correct
21 Correct 72 ms 27972 KB Output is correct
22 Correct 99 ms 22340 KB Output is correct
23 Correct 83 ms 20576 KB Output is correct
24 Correct 107 ms 22084 KB Output is correct
25 Correct 5 ms 7512 KB Output is correct
26 Correct 36 ms 13980 KB Output is correct
27 Correct 82 ms 20100 KB Output is correct
28 Correct 57 ms 24196 KB Output is correct
29 Correct 77 ms 27816 KB Output is correct
30 Correct 79 ms 27464 KB Output is correct
31 Correct 5 ms 7628 KB Output is correct