oj.uz

Submission #390914

# Submission time Handle Problem Language Result Execution time Memory
390914 2021-04-17T11:08:07 Z SavicS Factories (JOI14_factories) C++14
15 / 100
 8000 ms 108552 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;

set<int> s;

ll best[maxn];
void upd(int X) {
	for(int A = X ; A != 0 ; A = par[A]) {
		s.insert(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, 0);

	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 : s)best[c] = inf;
	s.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 71 ms 12452 KB Output is correct
2 Correct 3403 ms 21016 KB Output is correct
3 Correct 4971 ms 20984 KB Output is correct
4 Correct 5068 ms 21504 KB Output is correct
5 Correct 6374 ms 21448 KB Output is correct
6 Correct 1094 ms 21056 KB Output is correct
7 Correct 5025 ms 21036 KB Output is correct
8 Correct 5134 ms 21252 KB Output is correct
9 Correct 6354 ms 21348 KB Output is correct
10 Correct 1107 ms 21104 KB Output is correct
11 Correct 4983 ms 21108 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12236 KB Output is correct
2 Correct 5974 ms 106656 KB Output is correct
3 Execution timed out 8038 ms 108552 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 12452 KB Output is correct
2 Correct 3403 ms 21016 KB Output is correct
3 Correct 4971 ms 20984 KB Output is correct
4 Correct 5068 ms 21504 KB Output is correct
5 Correct 6374 ms 21448 KB Output is correct
6 Correct 1094 ms 21056 KB Output is correct
7 Correct 5025 ms 21036 KB Output is correct
8 Correct 5134 ms 21252 KB Output is correct
9 Correct 6354 ms 21348 KB Output is correct
10 Correct 1107 ms 21104 KB Output is correct
11 Correct 4983 ms 21108 KB Output is correct
12 Correct 15 ms 12236 KB Output is correct
13 Correct 5974 ms 106656 KB Output is correct
14 Execution timed out 8038 ms 108552 KB Time limit exceeded
15 Halted 0 ms 0 KB -