oj.uz

Submission #951810

# Submission time Handle Problem Language Result Execution time Memory
951810 2024-03-22T17:13:08 Z JakobZorz Factories (JOI14_factories) C++17
18 / 100
 8000 ms 148692 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=700;
 
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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 33376 KB Output is correct
2 Correct 4368 ms 51292 KB Output is correct
3 Execution timed out 8010 ms 46932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 1167 ms 117624 KB Output is correct
3 Correct 2652 ms 120380 KB Output is correct
4 Correct 888 ms 118092 KB Output is correct
5 Correct 3283 ms 148692 KB Output is correct
6 Correct 1886 ms 121408 KB Output is correct
7 Correct 3494 ms 67664 KB Output is correct
8 Correct 1237 ms 67288 KB Output is correct
9 Correct 2577 ms 70996 KB Output is correct
10 Correct 2060 ms 68060 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 33376 KB Output is correct
2 Correct 4368 ms 51292 KB Output is correct
3 Execution timed out 8010 ms 46932 KB Time limit exceeded
4 Halted 0 ms 0 KB -