oj.uz

Submission #390909

# Submission time Handle Problem Language Result Execution time Memory
390909 2021-04-17T11:03:55 Z SavicS Factories (JOI14_factories) C++14
15 / 100
 8000 ms 109472 KB 
#include "factories.h"

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 500005;
const ll inf = 1e18 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, q;

vector<pii> g[maxn];

int par[maxn];

int cnt[maxn];
bool bio[maxn];
void dfs_size(int v, int p) {
	cnt[v] = 1;
	for(auto c : g[v]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		dfs_size(u, v);
		cnt[v] += cnt[u];
	}
}

int centroid(int v, int p, int vel) {
	for(auto c : g[v]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		if(cnt[u] > vel / 2)return centroid(u, v, vel);
	}
	return v;
}

void decompose(int v, int p) {
	dfs_size(v, p);

	int cen = centroid(v, p, cnt[v]);
	bio[cen] = 1;

	par[cen] = p;
	for(auto c : g[cen]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		decompose(u, cen);
	}

}

int d[maxn];
ll dist[maxn];
int deda[maxn][25];
void dfs(int v, int p) {
	deda[v][0] = p;
	ff(i,1,21)deda[v][i] = deda[deda[v][i - 1]][i - 1];
	for(auto c : g[v]) {
		int u = c.fi;
		int w = c.se;
		if(u != p) {
			d[u] = d[v] + 1;
			dist[u] = dist[v] + w;
			dfs(u, v);
		}
	}
}

int lca(int x, int y) {
	if(d[x] < d[y])swap(x, y);
	fb(i,21,0) {
		if((d[x] - d[y]) & (1 << i))x = deda[x][i];
	}
	fb(i,21,0) {
		if(deda[x][i] != deda[y][i]) {
			x = deda[x][i];
			y = deda[y][i];
		}
	}
	return (x == y ? x : deda[x][0]);
}

ll distance(int x, int y) {
	return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}


vector<int> pamti;

ll best[maxn];
void upd(int X) {
	for(int A = X ; A != 0 ; A = par[A]) {
		pamti.pb(A);
		best[A] = min(best[A], distance(A, X));
	}
}

ll kve(int X) {
	ll ans = inf;
	for(int A = X ; A != 0 ; A = par[A]) {
		ans = min(ans, best[A] + distance(A, X));
	}
	return ans;
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	ff(i,0,n - 2) {
		int u = A[i] + 1;
		int v = B[i] + 1;
		int w = D[i];
		g[u].pb({v, w});
		g[v].pb({u, w});
	}

	decompose(1, 0);
	dfs(1, -1);

	ff(i,1,n)best[i] = inf;
}

ll Query(int S, int X[], int T, int Y[]) {
	ff(i,0,S - 1) {
		int A = X[i] + 1;
		upd(A);
	}

	ll ans = inf;
	ff(i,0,T - 1) {
		int B = Y[i] + 1;
		ans = min(ans, kve(B));
	}

	for(auto c : pamti)best[c] = inf;
	pamti.clear();

	return ans;

}

//int main()
//{
//    ios::sync_with_stdio(false);
//    cout.tie(nullptr);
//    cin.tie(nullptr);
//	cin >> n >> q;
//	ff(i,1,n - 1){
//		int u, v, w;
//		cin >> u >> v >> w;
//		u++, v++;
//		g[u].pb({v, w});
//		g[v].pb({u, w});
//	}
//
//	decompose(1, -1);
//	dfs(1, -1);
//
//	ff(i,1,n)best[i] = inf;
//
//	while(q--){
//		int S, T;
//		cin >> S >> T;
//
//		ff(i,1,S){
//			int X;
//			cin >> X;
//			X++;
//			upd(X);
//		}
//
//		ll ans = inf;
//		ff(i,1,T){
//			int X;
//			cin >> X;
//			X++;
//			ans = min(ans, kve(X));
//		}
//
//		for(auto c : pamti)best[c] = inf;
//		pamti.clear();
//
//	}
//
//    return 0;
//}
///**
//
//
//
//// probati bojenje sahovski ili slicno
//
//**/

Compilation message

factories.cpp: In function 'void dfs_size(int, int)':
factories.cpp:41:7: warning: unused variable 'w' [-Wunused-variable]
   41 |   int w = c.se;
      |       ^
factories.cpp: In function 'int centroid(int, int, int)':
factories.cpp:51:7: warning: unused variable 'w' [-Wunused-variable]
   51 |   int w = c.se;
      |       ^
factories.cpp: In function 'void decompose(int, int)':
factories.cpp:67:7: warning: unused variable 'w' [-Wunused-variable]
   67 |   int w = c.se;
      |       ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12468 KB Output is correct
2 Correct 2735 ms 30468 KB Output is correct
3 Correct 4104 ms 30536 KB Output is correct
4 Correct 4040 ms 30792 KB Output is correct
5 Correct 5236 ms 31020 KB Output is correct
6 Correct 944 ms 30392 KB Output is correct
7 Correct 4054 ms 30416 KB Output is correct
8 Correct 4270 ms 30456 KB Output is correct
9 Correct 5149 ms 30892 KB Output is correct
10 Correct 948 ms 30396 KB Output is correct
11 Correct 4027 ms 30532 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12236 KB Output is correct
2 Correct 5320 ms 107876 KB Output is correct
3 Execution timed out 8092 ms 109472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12468 KB Output is correct
2 Correct 2735 ms 30468 KB Output is correct
3 Correct 4104 ms 30536 KB Output is correct
4 Correct 4040 ms 30792 KB Output is correct
5 Correct 5236 ms 31020 KB Output is correct
6 Correct 944 ms 30392 KB Output is correct
7 Correct 4054 ms 30416 KB Output is correct
8 Correct 4270 ms 30456 KB Output is correct
9 Correct 5149 ms 30892 KB Output is correct
10 Correct 948 ms 30396 KB Output is correct
11 Correct 4027 ms 30532 KB Output is correct
12 Correct 14 ms 12236 KB Output is correct
13 Correct 5320 ms 107876 KB Output is correct
14 Execution timed out 8092 ms 109472 KB Time limit exceeded
15 Halted 0 ms 0 KB -