oj.uz

Submission #934981

# Submission time Handle Problem Language Result Execution time Memory
934981 2024-02-28T09:45:38 Z Baizho Factories (JOI14_factories) C++17
15 / 100
 8000 ms 199764 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;


ll n, m, par[M + 10], siz[M + 10], up[20][M + 10], col[M + 10];
bool del[M + 10];
long long dis[M + 10], depth[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 35 ms 78416 KB Output is correct
2 Correct 573 ms 82768 KB Output is correct
3 Correct 1226 ms 92428 KB Output is correct
4 Correct 1163 ms 90380 KB Output is correct
5 Correct 1288 ms 90880 KB Output is correct
6 Correct 212 ms 92240 KB Output is correct
7 Correct 1187 ms 90392 KB Output is correct
8 Correct 1282 ms 90232 KB Output is correct
9 Correct 1341 ms 90708 KB Output is correct
10 Correct 223 ms 90192 KB Output is correct
11 Correct 1192 ms 90392 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 76380 KB Output is correct
2 Correct 3487 ms 151284 KB Output is correct
3 Correct 6819 ms 173000 KB Output is correct
4 Correct 734 ms 170452 KB Output is correct
5 Execution timed out 8064 ms 199764 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 78416 KB Output is correct
2 Correct 573 ms 82768 KB Output is correct
3 Correct 1226 ms 92428 KB Output is correct
4 Correct 1163 ms 90380 KB Output is correct
5 Correct 1288 ms 90880 KB Output is correct
6 Correct 212 ms 92240 KB Output is correct
7 Correct 1187 ms 90392 KB Output is correct
8 Correct 1282 ms 90232 KB Output is correct
9 Correct 1341 ms 90708 KB Output is correct
10 Correct 223 ms 90192 KB Output is correct
11 Correct 1192 ms 90392 KB Output is correct
12 Correct 12 ms 76380 KB Output is correct
13 Correct 3487 ms 151284 KB Output is correct
14 Correct 6819 ms 173000 KB Output is correct
15 Correct 734 ms 170452 KB Output is correct
16 Execution timed out 8064 ms 199764 KB Time limit exceeded
17 Halted 0 ms 0 KB -