oj.uz

Submission #934988

# Submission time Handle Problem Language Result Execution time Memory
934988 2024-02-28T09:47:54 Z Baizho Factories (JOI14_factories) C++17
33 / 100
 8000 ms 149780 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
 
 #pragma GCC optimize("Ofast,unroll-loops,fast-math")
 #pragma GCC target("popcnt")
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int 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 long long inf = 5e18;
const long double eps = 1e-15L;
const int M = 5e5 + 10;


int n, m, par[M + 10], siz[M + 10], up[20][M + 10], col[M + 10], depth[M + 10];
bool del[M + 10];
long long dis[M + 10], wei[M + 10];
vector<pair<int, int> > g[M + 10];
 
void qfs(int v, int p = 0) {
	depth[v] = depth[p] + 1;
	dis[v] = inf;
	up[0][v] = p;
	for(int j = 1; j <= 19; j ++) up[j][v] = up[j - 1][up[j - 1][v]];
	for(auto to : g[v]) {
		if(to.ff == p) continue;
		wei[to.ff] = wei[v] + to.ss;
		qfs(to.ff, v);
	}
}
 
void dfs_size(int v, int p = -1) {
	siz[v] = 1;
	for(auto to : g[v]) {
		if(to.ff == p || del[to.ff]) continue;
		dfs_size(to.ff, v);
		siz[v] += siz[to.ff];
	}
}
 
int getc(int v, int n, int p = -1) {
//	cout<<v<<" yolo  "<<n<<endl;
	for(auto to : g[v]) {
		if(to.ff == p || del[to.ff] || siz[to.ff] <= n / 2) continue;
		return getc(to.ff, n, v);
	}
//	cout<<v<<endl;
	return v;
}
 
void decomp(int v, int p = 0) {
	dfs_size(v);
//	cout<<v<<" "<<p<<endl;
	int c = getc(v, siz[v]);
//	cout<<c<<" "<<endl;
	par[c] = p;
	del[c] = 1;
	for(auto to : g[c]) {
		if(del[to.ff]) continue;
		decomp(to.ff, c);
	}
}
 
int lca(int u, int v) {
	if(depth[u] < depth[v]) swap(u, v);
//	cout<<u<<" "<<v<<" "<<" "<<depth[u]<<" "<<depth[v]<<" ";
	int dif = depth[u] - depth[v];
	for(int j = 19; j >= 0; j --) {
		if(dif & (1 << j)) u = up[j][u];
	}
//	cout<<u<<" ";
	if(u == v) return u;
	for(int j = 19; j >= 0; j --) {
		if(up[j][u] != up[j][v]) {
			u  = up[j][u]; v = up[j][v];
		}
	}
//	cout<<up[0][u]<<"\n";
	return up[0][u];
}
 
long long dist(int u, int v) {
//	cout<<u<<" "<<v<<" "<<depth[u] + depth[v] - depth[lca(u, v)] * 2<<"\n";
	return wei[u] + wei[v] - wei[lca(u, v)] * 2;
}
 
void add(long long v) {
	long long x = v;
	while(v > 0) {
//		cout<<v<<" her1 "<<endl;
//		cout<<v<<" "<<dist(v, x)<<" "<<dis[v]<<" yolo \n"<<endl;
		dis[v] = min(dis[v], dist(v, x));
		v = par[v];
	}
}
 
void erase(long long v) {
	long long x = v;
	while(v > 0) {
//		cout<<v<<" her2 "<<endl;
//		cout<<v<<" "<<dist(v, x)<<" "<<dis[v]<<" yolo \n";
		dis[v] = inf;
		v = par[v];
	}
}
 
long long get(int v) {
	long long ans = inf, x = v;
	while(v > 0) {
//		cout<<v<<" her3 "<<endl;
		ans = min(ans, dist(v, x) + dis[v]);
		v = par[v];
	}
	return ans;
}
 
void Init(int N, int A[], int B[], int D[]) {
//	cout<<N<<endl;
	n = N;
//	cout<<"YOLO "<<endl;
	for(int i = 0; i <= n - 2; i ++) {
		A[i] ++;
		B[i] ++;
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}
	qfs(1);
	decomp(1);
//	for(int i = 1; i <= n; i ++) cout<<par[i]<<" ";
//	cout<<"\n";
}
 
long long Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < S; i ++) {
		X[i] ++;
		add(X[i]);
	}
	long long ans = inf;
	for(int i = 0; i < T; i ++) {
		Y[i] ++;
		ans = min(ans, get(Y[i]));
	}
//	cout<<"YOLO "<<endl;
	for(int i = 0; i < S; i ++) {
		erase(X[i]);
	}
	return ans;
}

Compilation message

factories.cpp: In function 'void erase(long long int)':
factories.cpp:114:12: warning: unused variable 'x' [-Wunused-variable]
  114 |  long long x = v;
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 76636 KB Output is correct
2 Correct 442 ms 85584 KB Output is correct
3 Correct 1012 ms 85524 KB Output is correct
4 Correct 921 ms 85700 KB Output is correct
5 Correct 1024 ms 86096 KB Output is correct
6 Correct 186 ms 85584 KB Output is correct
7 Correct 962 ms 86048 KB Output is correct
8 Correct 1002 ms 85844 KB Output is correct
9 Correct 1057 ms 85856 KB Output is correct
10 Correct 196 ms 85564 KB Output is correct
11 Correct 946 ms 85900 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 76380 KB Output is correct
2 Correct 2243 ms 118956 KB Output is correct
3 Correct 5293 ms 122252 KB Output is correct
4 Correct 542 ms 119504 KB Output is correct
5 Correct 6432 ms 149780 KB Output is correct
6 Correct 5572 ms 131904 KB Output is correct
7 Correct 2404 ms 102148 KB Output is correct
8 Correct 300 ms 101820 KB Output is correct
9 Correct 2347 ms 105428 KB Output is correct
10 Correct 2594 ms 102584 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 76636 KB Output is correct
2 Correct 442 ms 85584 KB Output is correct
3 Correct 1012 ms 85524 KB Output is correct
4 Correct 921 ms 85700 KB Output is correct
5 Correct 1024 ms 86096 KB Output is correct
6 Correct 186 ms 85584 KB Output is correct
7 Correct 962 ms 86048 KB Output is correct
8 Correct 1002 ms 85844 KB Output is correct
9 Correct 1057 ms 85856 KB Output is correct
10 Correct 196 ms 85564 KB Output is correct
11 Correct 946 ms 85900 KB Output is correct
12 Correct 11 ms 76380 KB Output is correct
13 Correct 2243 ms 118956 KB Output is correct
14 Correct 5293 ms 122252 KB Output is correct
15 Correct 542 ms 119504 KB Output is correct
16 Correct 6432 ms 149780 KB Output is correct
17 Correct 5572 ms 131904 KB Output is correct
18 Correct 2404 ms 102148 KB Output is correct
19 Correct 300 ms 101820 KB Output is correct
20 Correct 2347 ms 105428 KB Output is correct
21 Correct 2594 ms 102584 KB Output is correct
22 Correct 3462 ms 132756 KB Output is correct
23 Correct 3569 ms 134388 KB Output is correct
24 Execution timed out 8096 ms 135616 KB Time limit exceeded
25 Halted 0 ms 0 KB -