oj.uz

Submission #959008

# Submission time Handle Problem Language Result Execution time Memory
959008 2024-04-07T11:21:26 Z YassirSalama Factories (JOI14_factories) C++17
15 / 100
 8000 ms 201032 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)];
}
bool vis[MAXN];
int dfs1(int node, int p = -1) {
  if (vis[node]) return 0;
  sub[node] = 1;

  for (auto x: v[node]) {
    if (x.F != p) {
      sub[node] += dfs1(x.F, node);
    }
  }

  return sub[node];
}

int dfs2(int node, int p, int n) {
  for (auto x: v[node]) {
    if (x.F != p) {
      if (!vis[x.F] && sub[x.F] > n / 2) {
        return dfs2(x.F, node, n);
      }
    }
  }

  return node;
}
void build(int node = 0, int p = -1) {
  dfs1(node,node);

  int c = dfs2(node, -1, sub[node]);
  vis[c] = true;
  par[c] = p;

  for (auto x: v[c]) {
    if (!vis[x.F]) {
      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 20 ms 49752 KB Output is correct
2 Correct 567 ms 59176 KB Output is correct
3 Correct 1144 ms 59204 KB Output is correct
4 Correct 1095 ms 63780 KB Output is correct
5 Correct 1273 ms 64112 KB Output is correct
6 Correct 243 ms 63568 KB Output is correct
7 Correct 1114 ms 63920 KB Output is correct
8 Correct 1145 ms 63964 KB Output is correct
9 Correct 1287 ms 64108 KB Output is correct
10 Correct 224 ms 63764 KB Output is correct
11 Correct 1135 ms 63808 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 49752 KB Output is correct
2 Correct 2505 ms 159332 KB Output is correct
3 Correct 5142 ms 171896 KB Output is correct
4 Correct 1349 ms 168020 KB Output is correct
5 Execution timed out 8010 ms 201032 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49752 KB Output is correct
2 Correct 567 ms 59176 KB Output is correct
3 Correct 1144 ms 59204 KB Output is correct
4 Correct 1095 ms 63780 KB Output is correct
5 Correct 1273 ms 64112 KB Output is correct
6 Correct 243 ms 63568 KB Output is correct
7 Correct 1114 ms 63920 KB Output is correct
8 Correct 1145 ms 63964 KB Output is correct
9 Correct 1287 ms 64108 KB Output is correct
10 Correct 224 ms 63764 KB Output is correct
11 Correct 1135 ms 63808 KB Output is correct
12 Correct 10 ms 49752 KB Output is correct
13 Correct 2505 ms 159332 KB Output is correct
14 Correct 5142 ms 171896 KB Output is correct
15 Correct 1349 ms 168020 KB Output is correct
16 Execution timed out 8010 ms 201032 KB Time limit exceeded
17 Halted 0 ms 0 KB -