oj.uz

Submission #951814

# Submission time Handle Problem Language Result Execution time Memory
951814 2024-03-22T17:16:45 Z JakobZorz Factories (JOI14_factories) C++17
33 / 100
 8000 ms 132536 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=100;
 
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 33368 KB Output is correct
2 Correct 293 ms 41960 KB Output is correct
3 Correct 702 ms 41968 KB Output is correct
4 Correct 565 ms 41704 KB Output is correct
5 Correct 319 ms 42324 KB Output is correct
6 Correct 200 ms 41776 KB Output is correct
7 Correct 708 ms 41788 KB Output is correct
8 Correct 557 ms 41812 KB Output is correct
9 Correct 322 ms 42072 KB Output is correct
10 Correct 199 ms 41780 KB Output is correct
11 Correct 709 ms 41812 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 33116 KB Output is correct
2 Correct 1158 ms 99180 KB Output is correct
3 Correct 2326 ms 102764 KB Output is correct
4 Correct 819 ms 100020 KB Output is correct
5 Correct 3096 ms 130056 KB Output is correct
6 Correct 1777 ms 102936 KB Output is correct
7 Correct 3308 ms 53660 KB Output is correct
8 Correct 1214 ms 53584 KB Output is correct
9 Correct 2335 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 33368 KB Output is correct
2 Correct 293 ms 41960 KB Output is correct
3 Correct 702 ms 41968 KB Output is correct
4 Correct 565 ms 41704 KB Output is correct
5 Correct 319 ms 42324 KB Output is correct
6 Correct 200 ms 41776 KB Output is correct
7 Correct 708 ms 41788 KB Output is correct
8 Correct 557 ms 41812 KB Output is correct
9 Correct 322 ms 42072 KB Output is correct
10 Correct 199 ms 41780 KB Output is correct
11 Correct 709 ms 41812 KB Output is correct
12 Correct 8 ms 33116 KB Output is correct
13 Correct 1158 ms 99180 KB Output is correct
14 Correct 2326 ms 102764 KB Output is correct
15 Correct 819 ms 100020 KB Output is correct
16 Correct 3096 ms 130056 KB Output is correct
17 Correct 1777 ms 102936 KB Output is correct
18 Correct 3308 ms 53660 KB Output is correct
19 Correct 1214 ms 53584 KB Output is correct
20 Correct 2335 ms 56916 KB Output is correct
21 Correct 1872 ms 54052 KB Output is correct
22 Correct 4848 ms 132208 KB Output is correct
23 Execution timed out 8089 ms 132536 KB Time limit exceeded
24 Halted 0 ms 0 KB -