oj.uz

Submission #764903

# Submission time Handle Problem Language Result Execution time Memory
764903 2023-06-24T06:25:41 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 538 ms 10836 KB 
#include <bits/stdc++.h>
using namespace std;
 
 #pragma comment(linker, "/stack:2000000000")
 #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define precise(a) cout<<fixed<<setprecision(a)
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
// t1
const ll mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const ll N = ll(5e4)+10;
const ll inf = 1e9;
const ld eps = 1e-15L;
const ll B = 400;
// const ld pie = acos(-1.0);
 
ll lcm(ll a, ll b){ return (a / __gcd(a,b))*b; }
ll binpow(ll a, ll b, ll m){ ll res=1;a%=m; while(b>0){ if(b&1)res=(res*a)%m; a=(a*a)%m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }

const int maxq = 10005;

int n, q, dis[N], ver[maxq][5], up[30][N], depth[N], used[N];
ll sum[N];
vector<int> need;
vector<pair<int, int> >g[N];

void dfs(int v, int p = -1) {
	if(p != -1) depth[v] = depth[p] + 1;
	up[0][v] = p;
	for(int j = 1; j<16; j++) up[j][v] = up[j-1][up[j-1][v]];
	for(auto got : g[v]) {
		int to = got.ff, w = got.ss;
		if(to == p) continue;
		dis[to] = dis[v] + w;
		dfs(to, v);
	}
}

int lca(int u, int v) {
	if(depth[u] < depth[v]) swap(u, v);
	// u is more under than v
	int dif = depth[u] - depth[v];
	for(int j = 16; j>=0; j--) {
		if(dif & (1<<j)) {
			u = up[j][u];
		}
	}
	if(u == v) return u;
	for(int j = 16; j>=0; j--) {
		if(up[j][u] != up[j][v]) {
			u = up[j][u];
			v = up[j][v];
		}
	}
	return up[0][u];
}

ll dist(int u, int v) {
	return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}

void Baizho()
{
	cin>>n;
	for(int i = 1; i<=n-1; i++) {
		int u, v, w; cin>>u>>v>>w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	cin>>q;
	dfs(0);	
	for(int i = 1; i<=q; i++) {
		for(int j = 0; j<5; j++) {
			cin>>ver[i][j];
		}
		sort(ver[i], ver[i]+5);
		ll ans = inf;
		do {
			ll res = 0;
			for(int j = 0; j<4; j++) {
				int x = ver[i][j], y = ver[i][j+1];
				int z = lca(x, y);
				res += dist(x, z) + dist(y, z);
			}
			ans = min(ans, res);
		} while(next_permutation(ver[i], ver[i]+5));
		
		cout<<ans<<"\n";
	}
	
}

 
int main() {
 
//     Freopen("ladder");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//    precalc();
   
    int ttt = 1;
//    cin>>ttt;

    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message

roadsideadverts.cpp:4: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    4 |  #pragma comment(linker, "/stack:2000000000")
      | 
roadsideadverts.cpp: In function 'void Freopen(std::string)':
roadsideadverts.cpp:33:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:33:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".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 538 ms 8924 KB Output is correct
2 Correct 399 ms 10760 KB Output is correct
3 Correct 406 ms 10768 KB Output is correct
4 Correct 400 ms 10748 KB Output is correct
5 Correct 399 ms 10772 KB Output is correct
6 Correct 411 ms 10756 KB Output is correct
7 Correct 423 ms 10732 KB Output is correct
8 Correct 394 ms 10668 KB Output is correct
9 Correct 409 ms 10836 KB Output is correct
10 Correct 406 ms 10676 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 6920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 538 ms 8924 KB Output is correct
3 Correct 399 ms 10760 KB Output is correct
4 Correct 406 ms 10768 KB Output is correct
5 Correct 400 ms 10748 KB Output is correct
6 Correct 399 ms 10772 KB Output is correct
7 Correct 411 ms 10756 KB Output is correct
8 Correct 423 ms 10732 KB Output is correct
9 Correct 394 ms 10668 KB Output is correct
10 Correct 409 ms 10836 KB Output is correct
11 Correct 406 ms 10676 KB Output is correct
12 Incorrect 24 ms 6920 KB Output isn't correct
13 Halted 0 ms 0 KB -