oj.uz

Submission #621265

# Submission time Handle Problem Language Result Execution time Memory
621265 2022-08-03T16:08:58 Z AbdelmagedNour Factories (JOI14_factories) C++17
100 / 100
 5221 ms 161520 KB 
#include<bits/stdc++.h>
using namespace std;
#include "factories.h"
const int MAXN=500005;
int st[MAXN],en[MAXN],p[MAXN][20],id;
long long dis[MAXN],ans,INF=1e18;
vector<vector<pair<int,long long>>>adj,adj2;

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;
}
pair<long long,long long>solve(int v,int par,map<int,int>&mp){
    pair<long long,long long>cur=make_pair(INF, INF);
    if(mp[v]==1)cur.first=0;
    if(mp[v]==2)cur.second=0;
    for(auto[u,w]:adj2[v]){
        if(u==par)continue;
        auto f=solve(u,v,mp);
        f.first+=w;
        f.second+=w;
        ans=min(ans,cur.first+f.second);
        ans=min(ans,cur.second+f.first);
        cur.first=min(cur.first,f.first);
        cur.second=min(cur.second,f.second);
    }
    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[]) {
    map<int,int>mp;
    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=0;i<temp_sz;i++){
        v.push_back(LCA(v[i],v[(i+1)%temp_sz]));
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    sort(v.begin(),v.end(),[&](int i,int j){
            return st[i]<st[j];
        });
    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]);
    }
    ans=LLONG_MAX;
    solve(v[0],-1,mp);
    return ans;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 756 KB Output is correct
2 Correct 1676 ms 9988 KB Output is correct
3 Correct 1695 ms 9828 KB Output is correct
4 Correct 1637 ms 10028 KB Output is correct
5 Correct 1331 ms 9996 KB Output is correct
6 Correct 1387 ms 9928 KB Output is correct
7 Correct 1698 ms 9888 KB Output is correct
8 Correct 1648 ms 10072 KB Output is correct
9 Correct 1398 ms 9992 KB Output is correct
10 Correct 1493 ms 9792 KB Output is correct
11 Correct 1924 ms 9644 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 1867 ms 123336 KB Output is correct
3 Correct 2553 ms 126508 KB Output is correct
4 Correct 1302 ms 120708 KB Output is correct
5 Correct 1507 ms 156008 KB Output is correct
6 Correct 2340 ms 128316 KB Output is correct
7 Correct 2205 ms 34444 KB Output is correct
8 Correct 1263 ms 33736 KB Output is correct
9 Correct 1156 ms 39316 KB Output is correct
10 Correct 2107 ms 35528 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 756 KB Output is correct
2 Correct 1676 ms 9988 KB Output is correct
3 Correct 1695 ms 9828 KB Output is correct
4 Correct 1637 ms 10028 KB Output is correct
5 Correct 1331 ms 9996 KB Output is correct
6 Correct 1387 ms 9928 KB Output is correct
7 Correct 1698 ms 9888 KB Output is correct
8 Correct 1648 ms 10072 KB Output is correct
9 Correct 1398 ms 9992 KB Output is correct
10 Correct 1493 ms 9792 KB Output is correct
11 Correct 1924 ms 9644 KB Output is correct
12 Correct 5 ms 468 KB Output is correct
13 Correct 1867 ms 123336 KB Output is correct
14 Correct 2553 ms 126508 KB Output is correct
15 Correct 1302 ms 120708 KB Output is correct
16 Correct 1507 ms 156008 KB Output is correct
17 Correct 2340 ms 128316 KB Output is correct
18 Correct 2205 ms 34444 KB Output is correct
19 Correct 1263 ms 33736 KB Output is correct
20 Correct 1156 ms 39316 KB Output is correct
21 Correct 2107 ms 35528 KB Output is correct
22 Correct 4453 ms 137512 KB Output is correct
23 Correct 3622 ms 136532 KB Output is correct
24 Correct 5221 ms 143240 KB Output is correct
25 Correct 4930 ms 146248 KB Output is correct
26 Correct 4632 ms 133252 KB Output is correct
27 Correct 3415 ms 161520 KB Output is correct
28 Correct 2888 ms 132620 KB Output is correct
29 Correct 4188 ms 132268 KB Output is correct
30 Correct 4229 ms 131728 KB Output is correct
31 Correct 4214 ms 132156 KB Output is correct
32 Correct 2219 ms 46908 KB Output is correct
33 Correct 2209 ms 41396 KB Output is correct
34 Correct 2707 ms 33864 KB Output is correct
35 Correct 2560 ms 33592 KB Output is correct
36 Correct 2891 ms 34588 KB Output is correct
37 Correct 2793 ms 34456 KB Output is correct