oj.uz

Submission #874968

# Submission time Handle Problem Language Result Execution time Memory
874968 2023-11-18T10:57:33 Z YassirSalama Factories (JOI14_factories) C++17
33 / 100
 8000 ms 194280 KB 
#include"factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
#include<assert.h>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
const int MAXN=5e5+100;
const int LOGN=21;
int up[MAXN][LOGN];
set<pair<int,int>> v[MAXN];
ll depth[MAXN];
int depth1[MAXN];
int par[MAXN];
int sub[MAXN];
bool visited[MAXN];
ll ans[MAXN];
void dfs(int node,int par){
	depth1[node]=depth1[par]+1;
	up[node][0]=par;
	for(int i=1;i<LOGN;i++){
		up[node][i]=up[up[node][i-1]][i-1];
	}
	for(auto x:v[node]){
		if(x.F==par) continue;
		depth[x.F]=depth[node]+x.S;
		dfs(x.F,node);
	}
}
int LCA(int a,int b){
	if(depth1[a]<depth1[b]) swap(a,b);
	ll d=depth1[a]-depth1[b];
	for(ll i=LOGN-1;i>=0;i--){
		if(d&(1<<i)) a=up[a][i]; 
	}
	if(a==b) return a;
	for(ll i=LOGN-1;i>=0;i--){
		if(up[a][i]==up[b][i]) continue;
		a=up[a][i];
		b=up[b][i];
	}
	return up[a][0];
}
ll dist(int a,int b){
	return depth[a]+depth[b]-2*depth[LCA(a,b)];
}
int dfs1(int node,int par){
	sub[node]=1;
	for(auto x:v[node]) {
	    if(x.F==par) continue;
	    sub[node]+=dfs1(x.F,node);
	}
	return sub[node];
}
int dfs2(int node,int par,int n){
	for(auto x:v[node]){
		if(x.F!=par&&sub[x.F]>n/2)
			return dfs2(x.F,node,n);
	}
	return node;
}
void build(int u, int p) {
  int n = dfs1(u, p);
  int c = dfs2(u, p, n);
  if(p == -1) p = -1;
  par[c] = p;

  vector<pair<int,int>> tmp(v[c].begin(), v[c].end());
  for(auto x : tmp) {
    v[c].erase({x.F,x.S}); v[x.F].erase({c,x.S});
    build(x.F, c);
  }
}
void Init(int N, int A[], int B[], int D[]){
	for(int i=0;i<N-1;i++){
		v[A[i]].insert({B[i],D[i]});
		v[B[i]].insert({A[i],D[i]});
	}
	dfs(0,0);
	build(0,-1);
	for(int i=0;i<=N;i++) ans[i]=1e18;
}
void clear(int x){
	int node=x;
	while(node!=-1){
		ans[node]=1e18;
		node=par[node];
	}
}
// void update(int x){
// 	int node=x;
// 	while(node!=-1){
// 		ans[node]=min(ans[node],dist(x,node));
// 		node=par[node];
// 	}
// }
// ll query(int x){
// 	ll anss=1e18;
// 	int node=x;
// 	while(node!=-1){
// 		anss=min(anss,ans[node]+dist(x,node));
// 		node=par[node];
// 	}
// 	return anss;
// }
long long Query(int S, int X[], int T, int Y[]){
	ll anss=1e18;
	for(int i=0;i<T;i++){
		int node=Y[i];
		while(node!=-1){
			ans[node]=min(ans[node],dist(Y[i],node));
			node=par[node];
		}
	}
	for(int i=0;i<S;i++) {
		int node=X[i];
		while(node!=-1){
			anss=min(anss,ans[node]+dist(X[i],node));
			node=par[node];
		}
	}
	for(int i=0;i<T;i++){
		int node=Y[i];
		while(node!=-1){
			if(ans[node]==1e18) break;
			ans[node]=1e18;
			node=par[node];
		}
	}	return anss;
}

#ifdef IOI


int main(){
	// Init(7, {0, 1, 2, 2, 4, 1}, {1, 2, 3, 4, 5, 6}, {4, 4, 5, 6, 5, 3});
	// cout<<Query(2, 2, {0, 6}, {3, 4}); //returns 12.
	// cout<<endl<<Query(3, 2, {0, 1, 3}, {4, 6}); //returns 3.
	// cout<<endl<<Query(1, 1, {2}, {5}); //returns 11.
	// return 0;
    int N, Q;
    assert(scanf("%i %i", &N, &Q) == 2);
    int *A = (int*)malloc(sizeof(int) * (N - 1));
    int *B = (int*)malloc(sizeof(int) * (N - 1));
    int *D = (int*)malloc(sizeof(int) * (N - 1));
    for(int a = 0; a < N - 1; a++){
        assert(scanf("%i %i %i", A + a, B + a, D + a) == 3);
    }
    Init(N, A, B, D);
    for(int a = 0; a < Q; a++){
        int S, T;
        assert(scanf("%i %i", &S, &T) == 2);
        int *X = (int*)malloc(sizeof(int) * S);
        int *Y = (int*)malloc(sizeof(int) * T);
        for(int b = 0; b < S; b++){
            assert(scanf("%i", X + b) == 1);
        }
        for(int b = 0; b < T; b++){
            assert(scanf("%i", Y + b) == 1);
        }
        printf("%i\n", Query(S, X, T, Y));
        free(X);
        free(Y);
    }
    free(A);
    free(B);
    free(D);
}
#endif

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47704 KB Output is correct
2 Correct 564 ms 57416 KB Output is correct
3 Correct 1134 ms 57212 KB Output is correct
4 Correct 1056 ms 57204 KB Output is correct
5 Correct 1260 ms 57684 KB Output is correct
6 Correct 210 ms 57172 KB Output is correct
7 Correct 1101 ms 57260 KB Output is correct
8 Correct 1145 ms 57228 KB Output is correct
9 Correct 1293 ms 57572 KB Output is correct
10 Correct 212 ms 57232 KB Output is correct
11 Correct 1111 ms 57212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47704 KB Output is correct
2 Correct 2158 ms 158928 KB Output is correct
3 Correct 4546 ms 161840 KB Output is correct
4 Correct 1319 ms 158808 KB Output is correct
5 Correct 7820 ms 186124 KB Output is correct
6 Correct 4820 ms 162276 KB Output is correct
7 Correct 2560 ms 82888 KB Output is correct
8 Correct 383 ms 82480 KB Output is correct
9 Correct 2785 ms 85996 KB Output is correct
10 Correct 2800 ms 83480 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47704 KB Output is correct
2 Correct 564 ms 57416 KB Output is correct
3 Correct 1134 ms 57212 KB Output is correct
4 Correct 1056 ms 57204 KB Output is correct
5 Correct 1260 ms 57684 KB Output is correct
6 Correct 210 ms 57172 KB Output is correct
7 Correct 1101 ms 57260 KB Output is correct
8 Correct 1145 ms 57228 KB Output is correct
9 Correct 1293 ms 57572 KB Output is correct
10 Correct 212 ms 57232 KB Output is correct
11 Correct 1111 ms 57212 KB Output is correct
12 Correct 9 ms 47704 KB Output is correct
13 Correct 2158 ms 158928 KB Output is correct
14 Correct 4546 ms 161840 KB Output is correct
15 Correct 1319 ms 158808 KB Output is correct
16 Correct 7820 ms 186124 KB Output is correct
17 Correct 4820 ms 162276 KB Output is correct
18 Correct 2560 ms 82888 KB Output is correct
19 Correct 383 ms 82480 KB Output is correct
20 Correct 2785 ms 85996 KB Output is correct
21 Correct 2800 ms 83480 KB Output is correct
22 Correct 2943 ms 148804 KB Output is correct
23 Correct 3043 ms 149588 KB Output is correct
24 Correct 7617 ms 151116 KB Output is correct
25 Correct 7211 ms 177708 KB Output is correct
26 Correct 7263 ms 175832 KB Output is correct
27 Execution timed out 8022 ms 194280 KB Time limit exceeded
28 Halted 0 ms 0 KB -