oj.uz

Submission #621272

# Submission time Handle Problem Language Result Execution time Memory
621272 2022-08-03T16:14:54 Z AbdelmagedNour Factories (JOI14_factories) C++17
100 / 100
 3100 ms 160548 KB 
#include<bits/stdc++.h>
using namespace std;
//#include"grader.cpp"
#include "factories.h"
const int MAXN=500005;
int st[MAXN],en[MAXN],p[MAXN][20],mp[MAXN],id;
long long dis[MAXN];
vector<vector<pair<int,long long>>>adj,adj2;
struct node{
    long long ans,blue,red;
    node(){
        ans=LLONG_MAX;
        blue=red=1e18;
    }
    node(long long a,long long b,long long c){
        ans=a;red=b;blue=c;
    }
};
node Merge(node&par,node&ch){
    long long ans,red,blue;
    ans=min({par.ans,ch.ans,par.blue+ch.red,par.red+ch.blue});
    red=min(par.red,ch.red);
    blue=min(par.blue,ch.blue);
    return node(ans,red,blue);
}
void dfs(int v,int par=0,long long dist=0){
    st[v]=++id;
    p[v][0]=par;
    dis[v]=dist;
    for(int i=1;i<20;i++)p[v][i]=p[p[v][i-1]][i-1];
    for(auto&[u,w]:adj[v]){
        if(u==par)continue;
        dfs(u,v,dist+w);
    }
    en[v]=id;
}
node dfs2(int v,int par){
    node cur=node();
    if(mp[v]==1)cur.red=0;
    else if(mp[v]==2)cur.blue=0;
    for(auto&[u,w]:adj2[v]){
        if(u==par)continue;
        node New=dfs2(u,v);
        New.red+=w;
        New.blue+=w;
        cur=Merge(cur,New);
    }
    return cur;
}
bool is_ancestor(int u,int v){
    return st[u]<=st[v]&&en[u]>=en[v];
}
int LCA(int u,int v){
    if(is_ancestor(u,v))return u;
    if(is_ancestor(v,u))return v;
    for(int i=19;i>=0;i--){
        if(is_ancestor(p[u][i],v))continue;
        u=p[u][i];
    }
    return p[u][0];
}
long long cost(int u,int v){
    return dis[u]+dis[v]-2*dis[LCA(u,v)];
}
void Init(int N, int A[], int B[], int D[]) {
    id=-1;
    adj.resize(N);
    adj2.resize(N);
    for(int i=0;i<N-1;i++){
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    dfs(0);
}
long long Query(int S, int X[], int T, int Y[]) {
    vector<int>v;
    for(int i=0;i<S;i++){
        mp[X[i]]=1;
        v.push_back(X[i]);
    }
    for(int i=0;i<T;i++){
        mp[Y[i]]=2;
        v.push_back(Y[i]);
    }
    sort(v.begin(),v.end(),[&](int i,int j){
            return st[i]<st[j];
        });
    int temp_sz=v.size();
    for(int i=1;i<temp_sz;i++)v.push_back(LCA(v[i],v[i-1]));
    v.push_back(LCA(v[0],v[temp_sz-1]));
    sort(v.begin(),v.end(),[&](int i,int j){
            return st[i]<st[j];
        });
    v.resize(unique(v.begin(),v.end())-v.begin());
    for(int i=0;i<v.size();i++)adj2[v[i]].clear();
    vector<int>Stack;
    for(int i=0;i<v.size();i++){
        while(!Stack.empty()&&!is_ancestor(Stack.back(),v[i]))Stack.pop_back();
        if(!Stack.empty()){
            long long U=Stack.back(),V=v[i],C=cost(U,V);
            adj2[U].push_back({V,C});
            adj2[V].push_back({U,C});
        }
        Stack.push_back(v[i]);
    }
    long long res=dfs2(v[0],-1).ans;
    for(auto&cur:v)mp[cur]=0;
    return res;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<v.size();i++)adj2[v[i]].clear();
      |                 ~^~~~~~~~~
factories.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 724 KB Output is correct
2 Correct 810 ms 9596 KB Output is correct
3 Correct 842 ms 9644 KB Output is correct
4 Correct 790 ms 9980 KB Output is correct
5 Correct 634 ms 10092 KB Output is correct
6 Correct 645 ms 9644 KB Output is correct
7 Correct 846 ms 9696 KB Output is correct
8 Correct 823 ms 9924 KB Output is correct
9 Correct 608 ms 9940 KB Output is correct
10 Correct 653 ms 9528 KB Output is correct
11 Correct 861 ms 9720 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 1415 ms 125276 KB Output is correct
3 Correct 2013 ms 128496 KB Output is correct
4 Correct 1065 ms 122744 KB Output is correct
5 Correct 1349 ms 157892 KB Output is correct
6 Correct 2021 ms 130240 KB Output is correct
7 Correct 1603 ms 34852 KB Output is correct
8 Correct 935 ms 34152 KB Output is correct
9 Correct 781 ms 39680 KB Output is correct
10 Correct 1580 ms 36004 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 724 KB Output is correct
2 Correct 810 ms 9596 KB Output is correct
3 Correct 842 ms 9644 KB Output is correct
4 Correct 790 ms 9980 KB Output is correct
5 Correct 634 ms 10092 KB Output is correct
6 Correct 645 ms 9644 KB Output is correct
7 Correct 846 ms 9696 KB Output is correct
8 Correct 823 ms 9924 KB Output is correct
9 Correct 608 ms 9940 KB Output is correct
10 Correct 653 ms 9528 KB Output is correct
11 Correct 861 ms 9720 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 1415 ms 125276 KB Output is correct
14 Correct 2013 ms 128496 KB Output is correct
15 Correct 1065 ms 122744 KB Output is correct
16 Correct 1349 ms 157892 KB Output is correct
17 Correct 2021 ms 130240 KB Output is correct
18 Correct 1603 ms 34852 KB Output is correct
19 Correct 935 ms 34152 KB Output is correct
20 Correct 781 ms 39680 KB Output is correct
21 Correct 1580 ms 36004 KB Output is correct
22 Correct 2610 ms 135836 KB Output is correct
23 Correct 2375 ms 136048 KB Output is correct
24 Correct 2924 ms 139776 KB Output is correct
25 Correct 3100 ms 142532 KB Output is correct
26 Correct 3087 ms 134180 KB Output is correct
27 Correct 2383 ms 160548 KB Output is correct
28 Correct 1753 ms 130620 KB Output is correct
29 Correct 3059 ms 133112 KB Output is correct
30 Correct 3056 ms 132460 KB Output is correct
31 Correct 3049 ms 132992 KB Output is correct
32 Correct 1160 ms 45140 KB Output is correct
33 Correct 1158 ms 37040 KB Output is correct
34 Correct 1440 ms 34200 KB Output is correct
35 Correct 1431 ms 33808 KB Output is correct
36 Correct 1640 ms 34512 KB Output is correct
37 Correct 1619 ms 34512 KB Output is correct