oj.uz

Submission #765142

# Submission time Handle Problem Language Result Execution time Memory
765142 2023-06-24T08:42:33 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
70 / 100
 1000 ms 15552 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#pragma GCC optimization("g", on)
#pragma GCC optimization("03")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse,-fgcse-lm")
#pragma GCC optimize("-ftree-pre,-ftree-vrp")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define boba ios_base::sync_with_stdio(false); cin.tie(NULL);
#define br break
#define sp " "
#define en "\n"
#define pb push_back
#define sz size()
#define bg begin()
#define ed end()
#define in insert
#define ss second
#define ff first
#define rbg rbegin()
#define setp(a) cout << fixed; cout << setprecision(a);
#define all(v) v.begin(), v.end()
#define emp empty()
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef double db;
typedef tree<
    long long,
    null_type,
    less_equal<long long>,
    rb_tree_tag,
    tree_order_statistics_node_update> orset;

void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
ll bp(ll x, ll y, ll z) { ll res = 1; while (y) { if (y & 1) { res = (res * x) % z; y--; } x = (x * x) % z; y >>= 1; } return res; }
// C(n, k) = ((fact[n] * bp(fact[k], mod - 2)) % mod * bp(fact[n - k], mod - 2)) % mod;
ll lcm(ll a, ll b) { return (a / __gcd(a, b)) * b; }

const ll N = 5e4 + 11;	
const ll inf = 1e9 + 7;
ll tt = 1;
vector<pll> g[N];
ll d[N], pr[N];
ll up[N][17];
ll dp[N], c[N];

void dfs(ll v, ll p) {
	up[v][0] = p;
	for (int i = 1;i <= 16;i++) up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto to : g[v]) {
		if (to.ff != p) {
			d[to.ff] = d[v] + 1;
			pr[d[to.ff]] = pr[d[v]] + to.ss;
			dfs(to.ff, v);
		}
	}
}

void get(ll v, ll p) {
//	dp[v] = 0;
	for (auto to : g[v]) {
		if (to.ff != p) {
			get(to.ff, v);
			dp[v] += (dp[to.ff] + to.ss) * c[to.ff];
			c[v] |= c[to.ff];
		}
	}
//	cout << dp[v] << sp << c[v] << sp << v << en;
}

//10
//0 1 3
//0 2 4
//1 3 10
//1 4 7
//1 5 1
//5 6 0
//5 7 15
//2 8 1
//2 9 5
//5
//0 1 3 5 7
//2 5 3 7 9
//8 3 5 0 6
//3 4 5 8 9
//3 4 6 7 2

//7
//0 1 1
//1 2 3
//2 3 0
//3 4 5
//4 5 8
//5 6 3
//3
//1 2 3 4 5
//0 1 2 3 5
//1 2 4 5 6

ll lca(ll x, ll y) {
//	cout << x << sp << y << en;
	if (d[x] < d[y]) swap(x, y);
	ll k = d[x] - d[y];
	for (int i = 0;i < 17;i++) {
		if (k & (1 << i)) {
			x = up[x][i];
		}
	}
	if (x == y) return x;
	for (int i = 16;i >= 0;i--) {
		if (up[x][i] != up[y][i]) {
			x = up[x][i];
			y = up[y][i];
		}
	}
	return up[x][0];
}
	
void solve() {
	ll n; cin >> n;
	for (int i = 1;i < n;i++) {
		ll u, v, w; cin >> u >> v >> w;
		u++, v++;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	bool f = 0;
	ll rt = 0;
	for (int i = 1;i <= n;i++) {
		if (g[i].sz == 1) {
			if (!rt) rt = i;
		}
		if (g[i].sz > 2) f = 1;
	}
	if (f) rt = 1;
	d[rt] = 1;
	dfs(rt, 0);
	ll q; cin >> q;
	while (q--) {
		if (!f) {
			ll b[6]; 
			ll mn = inf, mx = 0;
			for (int i = 1;i <= 5;i++) {
				cin >> b[i];
				b[i]++;
				mn = min(mn, d[b[i]]);
				mx = max(mx, d[b[i]]);
			}
	//		cout << mn << sp << mx << en;
			cout << pr[mx] - pr[mn] << en;
			continue;
		}
		ll b[6];
		ll lc = 0;
		for (int i = 1;i <= n;i++) dp[i] = c[i] = 0;
		for (int i = 1;i <= 5;i++) {
			cin >> b[i];
			b[i]++;
			if (i == 1) {
				lc = b[1];
			}
			if (i > 1) lc = lca(lc, b[i]);
			c[b[i]] = 1;
		}
		get(lc, up[lc][0]);
		cout << dp[lc] << en;
	}
}	
  
int main() {    
   boba                                   
//    freopen("ladder");
//    precalc();
//    cin >> tt;	
	for (int i = 1;i <= tt;i++) {
		solve(); 
    }
}

Compilation message

roadsideadverts.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization("g", on)
      | 
roadsideadverts.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization("03")
      | 
roadsideadverts.cpp:9: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    9 | #pragma comment(linker, "/stack:200000000")
      | 
roadsideadverts.cpp: In function 'void freopen(std::string)':
roadsideadverts.cpp:49:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:49:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15220 KB Output is correct
2 Correct 37 ms 15476 KB Output is correct
3 Correct 31 ms 15480 KB Output is correct
4 Correct 34 ms 15444 KB Output is correct
5 Correct 32 ms 15444 KB Output is correct
6 Correct 29 ms 15552 KB Output is correct
7 Correct 32 ms 15412 KB Output is correct
8 Correct 31 ms 15496 KB Output is correct
9 Correct 31 ms 15480 KB Output is correct
10 Correct 31 ms 15488 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 11904 KB Output is correct
2 Correct 177 ms 15492 KB Output is correct
3 Correct 192 ms 15492 KB Output is correct
4 Correct 171 ms 15492 KB Output is correct
5 Correct 184 ms 15488 KB Output is correct
6 Correct 214 ms 15492 KB Output is correct
7 Correct 194 ms 15488 KB Output is correct
8 Correct 177 ms 15500 KB Output is correct
9 Correct 181 ms 15436 KB Output is correct
10 Correct 198 ms 15484 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 41 ms 15220 KB Output is correct
3 Correct 37 ms 15476 KB Output is correct
4 Correct 31 ms 15480 KB Output is correct
5 Correct 34 ms 15444 KB Output is correct
6 Correct 32 ms 15444 KB Output is correct
7 Correct 29 ms 15552 KB Output is correct
8 Correct 32 ms 15412 KB Output is correct
9 Correct 31 ms 15496 KB Output is correct
10 Correct 31 ms 15480 KB Output is correct
11 Correct 31 ms 15488 KB Output is correct
12 Correct 124 ms 11904 KB Output is correct
13 Correct 177 ms 15492 KB Output is correct
14 Correct 192 ms 15492 KB Output is correct
15 Correct 171 ms 15492 KB Output is correct
16 Correct 184 ms 15488 KB Output is correct
17 Correct 214 ms 15492 KB Output is correct
18 Correct 194 ms 15488 KB Output is correct
19 Correct 177 ms 15500 KB Output is correct
20 Correct 181 ms 15436 KB Output is correct
21 Correct 198 ms 15484 KB Output is correct
22 Correct 29 ms 15204 KB Output is correct
23 Execution timed out 1084 ms 11900 KB Time limit exceeded
24 Halted 0 ms 0 KB -