oj.uz

Submission #874963

# Submission time Handle Problem Language Result Execution time Memory
874963 2023-11-18T10:43:54 Z YassirSalama Factories (JOI14_factories) C++17
33 / 100
 8000 ms 195604 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);
  par[c] = p;

  // vector<pair<int,int>> tmp(v[c].begin(), v[c].end());
  for(auto x : v[c]) {
  	if(x.F==p) continue;
    // 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;
}
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]==(int)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 21 ms 47704 KB Output is correct
2 Correct 624 ms 61668 KB Output is correct
3 Correct 1259 ms 62060 KB Output is correct
4 Correct 1281 ms 62036 KB Output is correct
5 Correct 1404 ms 62288 KB Output is correct
6 Correct 236 ms 61780 KB Output is correct
7 Correct 1270 ms 61840 KB Output is correct
8 Correct 1281 ms 61828 KB Output is correct
9 Correct 1370 ms 62064 KB Output is correct
10 Correct 244 ms 61804 KB Output is correct
11 Correct 1236 ms 62068 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 2371 ms 167936 KB Output is correct
3 Correct 5051 ms 170540 KB Output is correct
4 Correct 1321 ms 167656 KB Output is correct
5 Correct 7935 ms 195604 KB Output is correct
6 Correct 5312 ms 171396 KB Output is correct
7 Correct 2714 ms 89396 KB Output is correct
8 Correct 431 ms 89312 KB Output is correct
9 Correct 3367 ms 92868 KB Output is correct
10 Correct 2808 ms 90256 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47704 KB Output is correct
2 Correct 624 ms 61668 KB Output is correct
3 Correct 1259 ms 62060 KB Output is correct
4 Correct 1281 ms 62036 KB Output is correct
5 Correct 1404 ms 62288 KB Output is correct
6 Correct 236 ms 61780 KB Output is correct
7 Correct 1270 ms 61840 KB Output is correct
8 Correct 1281 ms 61828 KB Output is correct
9 Correct 1370 ms 62064 KB Output is correct
10 Correct 244 ms 61804 KB Output is correct
11 Correct 1236 ms 62068 KB Output is correct
12 Correct 9 ms 47704 KB Output is correct
13 Correct 2371 ms 167936 KB Output is correct
14 Correct 5051 ms 170540 KB Output is correct
15 Correct 1321 ms 167656 KB Output is correct
16 Correct 7935 ms 195604 KB Output is correct
17 Correct 5312 ms 171396 KB Output is correct
18 Correct 2714 ms 89396 KB Output is correct
19 Correct 431 ms 89312 KB Output is correct
20 Correct 3367 ms 92868 KB Output is correct
21 Correct 2808 ms 90256 KB Output is correct
22 Correct 3366 ms 171840 KB Output is correct
23 Correct 3395 ms 174316 KB Output is correct
24 Execution timed out 8090 ms 175432 KB Time limit exceeded
25 Halted 0 ms 0 KB -