oj.uz

Submission #940615

# Submission time Handle Problem Language Result Execution time Memory
940615 2024-03-07T11:42:40 Z JakobZorz Factories (JOI14_factories) C++17
15 / 100
 8000 ms 126564 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];
int color[500000];
ll depth[500000];

void dfs1(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;
        dfs1(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]);
    }
    
    dfs1(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]);
}

ll Query(int n1,int arr1[],int n2,int arr2[]) {
    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;
}

#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 14 ms 37468 KB Output is correct
2 Correct 642 ms 51200 KB Output is correct
3 Correct 745 ms 51272 KB Output is correct
4 Correct 709 ms 51280 KB Output is correct
5 Correct 844 ms 51544 KB Output is correct
6 Correct 336 ms 51292 KB Output is correct
7 Correct 736 ms 51260 KB Output is correct
8 Correct 697 ms 51284 KB Output is correct
9 Correct 767 ms 51548 KB Output is correct
10 Correct 353 ms 51284 KB Output is correct
11 Correct 750 ms 51280 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37212 KB Output is correct
2 Execution timed out 8064 ms 126564 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37468 KB Output is correct
2 Correct 642 ms 51200 KB Output is correct
3 Correct 745 ms 51272 KB Output is correct
4 Correct 709 ms 51280 KB Output is correct
5 Correct 844 ms 51544 KB Output is correct
6 Correct 336 ms 51292 KB Output is correct
7 Correct 736 ms 51260 KB Output is correct
8 Correct 697 ms 51284 KB Output is correct
9 Correct 767 ms 51548 KB Output is correct
10 Correct 353 ms 51284 KB Output is correct
11 Correct 750 ms 51280 KB Output is correct
12 Correct 10 ms 37212 KB Output is correct
13 Execution timed out 8064 ms 126564 KB Time limit exceeded
14 Halted 0 ms 0 KB -