oj.uz

Submission #934986

# Submission time Handle Problem Language Result Execution time Memory
934986 2024-02-28T09:47:12 Z Baizho Factories (JOI14_factories) C++17
15 / 100
 8000 ms 137160 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 30 ms 76380 KB Output is correct
2 Correct 539 ms 80788 KB Output is correct
3 Correct 1202 ms 80860 KB Output is correct
4 Correct 1098 ms 80852 KB Output is correct
5 Correct 1237 ms 81148 KB Output is correct
6 Correct 215 ms 80776 KB Output is correct
7 Correct 1136 ms 80872 KB Output is correct
8 Correct 1159 ms 80876 KB Output is correct
9 Correct 1244 ms 81048 KB Output is correct
10 Correct 223 ms 81040 KB Output is correct
11 Correct 1148 ms 80872 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 76380 KB Output is correct
2 Correct 2739 ms 107436 KB Output is correct
3 Correct 6033 ms 111008 KB Output is correct
4 Correct 602 ms 108220 KB Output is correct
5 Execution timed out 8039 ms 137160 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 76380 KB Output is correct
2 Correct 539 ms 80788 KB Output is correct
3 Correct 1202 ms 80860 KB Output is correct
4 Correct 1098 ms 80852 KB Output is correct
5 Correct 1237 ms 81148 KB Output is correct
6 Correct 215 ms 80776 KB Output is correct
7 Correct 1136 ms 80872 KB Output is correct
8 Correct 1159 ms 80876 KB Output is correct
9 Correct 1244 ms 81048 KB Output is correct
10 Correct 223 ms 81040 KB Output is correct
11 Correct 1148 ms 80872 KB Output is correct
12 Correct 11 ms 76380 KB Output is correct
13 Correct 2739 ms 107436 KB Output is correct
14 Correct 6033 ms 111008 KB Output is correct
15 Correct 602 ms 108220 KB Output is correct
16 Execution timed out 8039 ms 137160 KB Time limit exceeded
17 Halted 0 ms 0 KB -