oj.uz

Submission #951816

# Submission time Handle Problem Language Result Execution time Memory
951816 2024-03-22T17:18:37 Z JakobZorz Factories (JOI14_factories) C++17
33 / 100
 8000 ms 130132 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
 
int n,q;
vector<pair<int,int>>nodes[500000];
int par[500000][20];
int depth1[500000];
ll depth[500000];
int color[500000];

const int SQRT=150;
 
void dfs(int node,int p){
    par[node][0]=p;
    for(int i=1;i<20;i++)
        par[node][i]=par[par[node][i-1]][i-1];
    for(auto[ne,w]:nodes[node]){
        if(ne==p)
            continue;
        depth[ne]=depth[node]+w;
        depth1[ne]=depth1[node]+1;
        dfs(ne,node);
    }
}
 
int get_parent(int node,int p){
    for(int i=0;i<20;i++){
        if(p&(1<<i)){
            node=par[node][i];
        }
    }
    return node;
}
 
int lca(int a,int b){
    if(depth1[a]<depth1[b])
        swap(a,b);
    a=get_parent(a,depth1[a]-depth1[b]);
    for(int i=19;i>=0;i--){
        if(par[a][i]!=par[b][i]){
            a=par[a][i];
            b=par[b][i];
        }
    }
    if(a!=b)
        a=par[a][0];
    return a;
}
 
ll dist(int a,int b){
    int l=lca(a,b);
    return depth[a]+depth[b]-2*depth[l];
}
 
void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0;i<n-1;i++){
        nodes[A[i]].emplace_back(B[i],D[i]);
        nodes[B[i]].emplace_back(A[i],D[i]);
    }
    
    dfs(0,0);
}

ll res;
ll highest1[500000],highest2[500000];
void dfs2(int node,int p){
    if(color[node]==1)
        highest1[node]=0;
    else
        highest1[node]=1e18;
    if(color[node]==2)
        highest2[node]=0;
    else
        highest2[node]=1e18;
    
    for(auto[ne,w]:nodes[node]){
        if(ne==p)
            continue;
        dfs2(ne,node);
        highest1[node]=min(highest1[node],highest1[ne]+w);
        highest2[node]=min(highest2[node],highest2[ne]+w);
    }
    
    if(color[node]==1)
        res=min(res,highest2[node]);
    if(color[node]==2)
        res=min(res,highest1[node]);
    if(color[node]==0)
        res=min(res,highest1[node]+highest2[node]);
}

long long Query(int n1, int arr1[], int n2, int arr2[]) {
    if(n1>SQRT||n2>SQRT){
        for(int i=0;i<n;i++)
            color[i]=0;
        for(int i=0;i<n1;i++)
            color[arr1[i]]=1;
        for(int i=0;i<n2;i++)
            color[arr2[i]]=2;
        res=1e18;
        dfs2(0,0);
        return res;
    }
    
    ll res=1e18;
    for(int i1=0;i1<n1;i1++){
        for(int i2=0;i2<n2;i2++){
            res=min(res,dist(arr1[i1],arr2[i2]));
        }
    }
    return res;
}
 
#ifdef JAKOB
void solve(){
    int n,q;
    cin>>n>>q;
    vector<int>a(n-1),b(n-1),d(n-1);
    for(int i=0;i<n-1;i++)
        cin>>a[i]>>b[i]>>d[i];
    Init(n,&a[0],&b[0],&d[0]);
    
    while(q--){
        int n1,n2;
        cin>>n1>>n2;
        vector<int>arr1(n1),arr2(n2);
        for(int&i:arr1)
            cin>>i;
        for(int&i:arr2)
            cin>>i;
        cout<<Query(n1,&arr1[0],n2,&arr2[0])<<"\n";
    }
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("/Users/jakob/cp_testing/test.txt","r",stdin);freopen("output.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}
 
#endif
 
/*
 
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5
 
 */

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 33116 KB Output is correct
2 Correct 305 ms 41756 KB Output is correct
3 Correct 734 ms 41780 KB Output is correct
4 Correct 530 ms 41776 KB Output is correct
5 Correct 331 ms 41952 KB Output is correct
6 Correct 224 ms 41708 KB Output is correct
7 Correct 755 ms 41792 KB Output is correct
8 Correct 524 ms 41692 KB Output is correct
9 Correct 336 ms 42072 KB Output is correct
10 Correct 213 ms 41772 KB Output is correct
11 Correct 706 ms 41944 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33112 KB Output is correct
2 Correct 1120 ms 99152 KB Output is correct
3 Correct 2280 ms 102840 KB Output is correct
4 Correct 825 ms 99852 KB Output is correct
5 Correct 3167 ms 130132 KB Output is correct
6 Correct 1728 ms 102740 KB Output is correct
7 Correct 3435 ms 53660 KB Output is correct
8 Correct 1212 ms 53580 KB Output is correct
9 Correct 2280 ms 56916 KB Output is correct
10 Correct 1872 ms 54052 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 33116 KB Output is correct
2 Correct 305 ms 41756 KB Output is correct
3 Correct 734 ms 41780 KB Output is correct
4 Correct 530 ms 41776 KB Output is correct
5 Correct 331 ms 41952 KB Output is correct
6 Correct 224 ms 41708 KB Output is correct
7 Correct 755 ms 41792 KB Output is correct
8 Correct 524 ms 41692 KB Output is correct
9 Correct 336 ms 42072 KB Output is correct
10 Correct 213 ms 41772 KB Output is correct
11 Correct 706 ms 41944 KB Output is correct
12 Correct 7 ms 33112 KB Output is correct
13 Correct 1120 ms 99152 KB Output is correct
14 Correct 2280 ms 102840 KB Output is correct
15 Correct 825 ms 99852 KB Output is correct
16 Correct 3167 ms 130132 KB Output is correct
17 Correct 1728 ms 102740 KB Output is correct
18 Correct 3435 ms 53660 KB Output is correct
19 Correct 1212 ms 53580 KB Output is correct
20 Correct 2280 ms 56916 KB Output is correct
21 Correct 1872 ms 54052 KB Output is correct
22 Correct 4853 ms 107968 KB Output is correct
23 Execution timed out 8036 ms 107860 KB Time limit exceeded
24 Halted 0 ms 0 KB -