oj.uz

답안 #764804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764804 2023-06-24T04:57:36 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 22 ms 6452 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];

void dfs(ll v, ll p) {
	for (auto to : g[v]) {
		if (to.ff != p) {
			d[to.ff] = d[v] + 1;
			pr[d[to.ff]] = pr[d[v]] + to.ss;
//			cout << d[to.ff] << sp << pr[d[to.ff]] << sp << to.ff << sp << v << en;
			dfs(to.ff, v);
		}
	}
}
	
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});
	}
	ll rt = 0;
	for (int i = 1;i <= n;i++) {
		if (g[i].sz == 1) {
			d[i] = 1;
			rt = i;
			dfs(i, 0);
			br;
		}
	}
	ll q; cin >> q;
	while (q--) {
		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;
	}
}	
  
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 solve()':
roadsideadverts.cpp:79:5: warning: variable 'rt' set but not used [-Wunused-but-set-variable]
   79 |  ll rt = 0;
      |     ^~
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 6100 KB Output is correct
2 Correct 21 ms 6416 KB Output is correct
3 Correct 20 ms 6356 KB Output is correct
4 Correct 20 ms 6356 KB Output is correct
5 Correct 21 ms 6332 KB Output is correct
6 Correct 22 ms 6452 KB Output is correct
7 Correct 21 ms 6420 KB Output is correct
8 Correct 20 ms 6416 KB Output is correct
9 Correct 21 ms 6420 KB Output is correct
10 Correct 20 ms 6408 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 18 ms 6100 KB Output is correct
3 Correct 21 ms 6416 KB Output is correct
4 Correct 20 ms 6356 KB Output is correct
5 Correct 20 ms 6356 KB Output is correct
6 Correct 21 ms 6332 KB Output is correct
7 Correct 22 ms 6452 KB Output is correct
8 Correct 21 ms 6420 KB Output is correct
9 Correct 20 ms 6416 KB Output is correct
10 Correct 21 ms 6420 KB Output is correct
11 Correct 20 ms 6408 KB Output is correct
12 Incorrect 18 ms 4444 KB Output isn't correct
13 Halted 0 ms 0 KB -