oj.uz

Submission #959014

# Submission time Handle Problem Language Result Execution time Memory
959014 2024-04-07T11:26:09 Z YassirSalama Factories (JOI14_factories) C++17
33 / 100
 8000 ms 185944 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;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#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);
  }
  vector<pair<int,int>>().swap(tmp);
}
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 18 ms 49756 KB Output is correct
2 Correct 460 ms 59452 KB Output is correct
3 Correct 1012 ms 59476 KB Output is correct
4 Correct 1012 ms 59204 KB Output is correct
5 Correct 1059 ms 59464 KB Output is correct
6 Correct 207 ms 59228 KB Output is correct
7 Correct 1055 ms 59208 KB Output is correct
8 Correct 1020 ms 59216 KB Output is correct
9 Correct 1038 ms 59464 KB Output is correct
10 Correct 185 ms 59108 KB Output is correct
11 Correct 1004 ms 59216 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49756 KB Output is correct
2 Correct 2047 ms 159120 KB Output is correct
3 Correct 4489 ms 161848 KB Output is correct
4 Correct 1326 ms 158724 KB Output is correct
5 Correct 6974 ms 185944 KB Output is correct
6 Correct 5006 ms 171428 KB Output is correct
7 Correct 2718 ms 91128 KB Output is correct
8 Correct 362 ms 90828 KB Output is correct
9 Correct 2883 ms 94424 KB Output is correct
10 Correct 2828 ms 91740 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49756 KB Output is correct
2 Correct 460 ms 59452 KB Output is correct
3 Correct 1012 ms 59476 KB Output is correct
4 Correct 1012 ms 59204 KB Output is correct
5 Correct 1059 ms 59464 KB Output is correct
6 Correct 207 ms 59228 KB Output is correct
7 Correct 1055 ms 59208 KB Output is correct
8 Correct 1020 ms 59216 KB Output is correct
9 Correct 1038 ms 59464 KB Output is correct
10 Correct 185 ms 59108 KB Output is correct
11 Correct 1004 ms 59216 KB Output is correct
12 Correct 10 ms 49756 KB Output is correct
13 Correct 2047 ms 159120 KB Output is correct
14 Correct 4489 ms 161848 KB Output is correct
15 Correct 1326 ms 158724 KB Output is correct
16 Correct 6974 ms 185944 KB Output is correct
17 Correct 5006 ms 171428 KB Output is correct
18 Correct 2718 ms 91128 KB Output is correct
19 Correct 362 ms 90828 KB Output is correct
20 Correct 2883 ms 94424 KB Output is correct
21 Correct 2828 ms 91740 KB Output is correct
22 Correct 2756 ms 172712 KB Output is correct
23 Correct 3142 ms 174088 KB Output is correct
24 Execution timed out 8050 ms 175152 KB Time limit exceeded
25 Halted 0 ms 0 KB -