oj.uz

답안 #390916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390916 2021-04-17T11:15:31 Z SavicS 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 108352 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, int Y) {
	for(int A = X ; A != 0 ; A = par[A]) {
		
		if(Y == 1)best[A] = min(best[A], distance(A, X));
		else best[A] = inf;
		 
	}
}

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, 1);
	}

	ll ans = inf;
	ff(i,0,T - 1) {
		int B = Y[i] + 1;
		ans = min(ans, kve(B));
	}
	
	ff(i,0,S - 1){
		int A = X[i] + 1;
		upd(A, -1);
	}
	
	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));
//		}
//		cout << ans << endl;
//		
//	}
//
//    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

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 12460 KB Output is correct
2 Correct 2744 ms 20988 KB Output is correct
3 Correct 4135 ms 20960 KB Output is correct
4 Correct 4070 ms 20976 KB Output is correct
5 Correct 5146 ms 21444 KB Output is correct
6 Correct 931 ms 20940 KB Output is correct
7 Correct 4083 ms 20948 KB Output is correct
8 Correct 4289 ms 20964 KB Output is correct
9 Correct 5110 ms 21208 KB Output is correct
10 Correct 943 ms 20932 KB Output is correct
11 Correct 4059 ms 21036 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12236 KB Output is correct
2 Correct 5386 ms 106564 KB Output is correct
3 Execution timed out 8096 ms 108352 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 12460 KB Output is correct
2 Correct 2744 ms 20988 KB Output is correct
3 Correct 4135 ms 20960 KB Output is correct
4 Correct 4070 ms 20976 KB Output is correct
5 Correct 5146 ms 21444 KB Output is correct
6 Correct 931 ms 20940 KB Output is correct
7 Correct 4083 ms 20948 KB Output is correct
8 Correct 4289 ms 20964 KB Output is correct
9 Correct 5110 ms 21208 KB Output is correct
10 Correct 943 ms 20932 KB Output is correct
11 Correct 4059 ms 21036 KB Output is correct
12 Correct 15 ms 12236 KB Output is correct
13 Correct 5386 ms 106564 KB Output is correct
14 Execution timed out 8096 ms 108352 KB Time limit exceeded
15 Halted 0 ms 0 KB -