oj.uz

Submission #959012

# Submission time Handle Problem Language Result Execution time Memory
959012 2024-04-07T11:25:11 Z YassirSalama Factories (JOI14_factories) C++17
0 / 100
 8000 ms 157024 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)];
}
bool vis[MAXN];
int dfs1(int node,int par){
    if(vis[node]) return sub[node];
    vis[node]=true;
    sub[node]=1;
    for(auto x:v[node]) {
        if(x.F==par||vis[x.F]) 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&&!vis[x.F]&&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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51548 KB Output is correct
2 Correct 664 ms 56144 KB Output is correct
3 Correct 7326 ms 56396 KB Output is correct
4 Correct 6781 ms 56392 KB Output is correct
5 Execution timed out 8058 ms 56836 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 51548 KB Output is correct
2 Correct 2043 ms 147688 KB Output is correct
3 Execution timed out 8102 ms 157024 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51548 KB Output is correct
2 Correct 664 ms 56144 KB Output is correct
3 Correct 7326 ms 56396 KB Output is correct
4 Correct 6781 ms 56392 KB Output is correct
5 Execution timed out 8058 ms 56836 KB Time limit exceeded
6 Halted 0 ms 0 KB -