oj.uz

Submission #1096992

# Submission time Handle Problem Language Result Execution time Memory
1096992 2024-10-05T16:27:17 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 2071 ms 198116 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int,long long>>> graph;
vector<vector<int>> sparse(20);
vector<int> in,out,first,depth,loga,col;
vector<long long> dist;
vector<long long> DP1,DP2;
void calc(int u,int p,long long &ans){
    DP1[u]=1e15,DP2[u]=1e15;
    if(col[u]==0){
        DP1[u]=0;
    }
    else if(col[u]==1){
        DP2[u]=0;
    }
    for(pair<int,long long> &x:graph[u]){
        int v=x.first;
        long long w=x.second;
        if(v!=p){
            calc(v,u,ans);
            DP1[u]=min(DP1[u],DP1[v]+w);
            DP2[u]=min(DP2[u],DP2[v]+w);
        }
    }
    ans=min(ans,DP1[u]+DP2[u]);
}
int tim=0;
void DFS(int u,int p){
    sparse[0].push_back(u);
    if(first[u]==-1){
        first[u]=sparse[0].size()-1;
    }
    in[u]=tim;
    tim++;
    for(pair<int,long long> &x:graph[u]){
        int v=x.first;
        long long w=x.second;
        if(v!=p){
            dist[v]=dist[u]+w;
            depth[v]=depth[u]+1;
            DFS(v,u);
        }
    }
    out[u]=tim-1;
    if(p!=-1){
        sparse[0].push_back(p);
    }
}
int cmp1(int u,int v){
    if(depth[u]<depth[v]){
        return u;
    }
    return v;
}
int LCA(int u,int v){
    int l=first[u],r=first[v];
    if(l>r){
        swap(l,r);
    }
    return cmp1(sparse[loga[r-l+1]][l],sparse[loga[r-l+1]][r-(1<<loga[r-l+1])+1]);
}
void Init(int n,int a[],int b[],int d[]){
    graph.resize(n);
    in.resize(n);
    out.resize(n);
    first.resize(n);
    dist.resize(n);
    depth.resize(n);
    DP1.resize(n);
    DP2.resize(n);
    col.resize(n);
    fill(first.begin(),first.end(),-1);
    fill(col.begin(),col.end(),-1);
    dist[1]=0;
    depth[1]=0;
    for(int i=0;i<n-1;i++){
        graph[a[i]].push_back({b[i],d[i]});
        graph[b[i]].push_back({a[i],d[i]});
    }
    DFS(0,-1);
    loga.resize(sparse[0].size()+1);
    loga[1]=0;
    for(int i=2;i<=sparse[0].size();i++){
        loga[i]=loga[i>>1]+1;
    }
    for(int i=1;i<20;i++){
        for(int j=0;j+(1<<i)<=sparse[0].size();j++){
            sparse[i].push_back(cmp1(sparse[i-1][j],sparse[i-1][j+(1<<(i-1))]));
        }
    }
    for(int i=0;i<n;i++){
        graph[i].clear();
        graph[i].resize(0);
    }
}
bool cmp2(int u,int v){
    return (in[u]<in[v]);
}
long long Query(int s,int x[],int t,int y[]){
    vector<int> c;
    for(int i=0;i<s;i++){
        c.push_back(x[i]);
        col[x[i]]=0;
    }
    for(int i=0;i<t;i++){
        c.push_back(y[i]);
        col[y[i]]=1;
    }
    sort(c.begin(),c.end(),cmp2);
    for(int i=1;i<s+t;i++){
        c.push_back(LCA(c[i],c[i-1]));
    }
    sort(c.begin(),c.end(),cmp2);
    c.erase(unique(c.begin(),c.end()),c.end());
    /*for(int i=0;i<c.size();i++){
        cout << c[i] << ' ';
    }
    cout << endl;*/
    stack<int> st;
    for(int i=0;i<c.size();i++){
        while(!st.empty()&&out[c[i]]>out[st.top()]){
            st.pop();
        }
        if(!st.empty()){
          //  cout << c[i] << ' ' << st.top() << ' ' << abs(dist[c[i]]-dist[st.top()]) << endl;
            graph[c[i]].push_back({st.top(),abs(dist[c[i]]-dist[st.top()])});
            graph[st.top()].push_back({c[i],abs(dist[c[i]]-dist[st.top()])});
        }
        st.push(c[i]);
    }
    long long ans=1e18;
    calc(c[0],-1,ans);
    for(int i=0;i<c.size();i++){
        graph[c[i]].clear();
        graph[c[i]].resize(0);
    }
    for(int i=0;i<s;i++){
        col[x[i]]=-1;
    }
    for(int i=0;i<t;i++){
        col[y[i]]=-1;
    }
    return ans;
}
/*signed main(){
    int n,q;
    cin >> n >> q;
    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,b,d);
    while(q--){
        int s,t;
        cin >> s >> t;
        int x[s],y[t];
        for(int i=0;i<s;i++){
            cin >> x[i];
        }
        for(int i=0;i<t;i++){
            cin >> y[i];
        }
        cout << Query(s,x,t,y) << endl;
    }
}*/

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=2;i<=sparse[0].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~
factories.cpp:88:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int j=0;j+(1<<i)<=sparse[0].size();j++){
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i=0;i<c.size();i++){
      |                 ~^~~~~~~~~
factories.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for(int i=0;i<c.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 860 KB Output is correct
2 Correct 756 ms 18952 KB Output is correct
3 Correct 677 ms 19116 KB Output is correct
4 Correct 722 ms 19028 KB Output is correct
5 Correct 697 ms 19320 KB Output is correct
6 Correct 411 ms 19024 KB Output is correct
7 Correct 628 ms 19052 KB Output is correct
8 Correct 702 ms 19280 KB Output is correct
9 Correct 709 ms 19296 KB Output is correct
10 Correct 403 ms 19028 KB Output is correct
11 Correct 624 ms 19116 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 997 ms 170804 KB Output is correct
3 Correct 950 ms 172296 KB Output is correct
4 Correct 751 ms 168432 KB Output is correct
5 Correct 946 ms 191788 KB Output is correct
6 Correct 1014 ms 174324 KB Output is correct
7 Correct 707 ms 51464 KB Output is correct
8 Correct 456 ms 51812 KB Output is correct
9 Correct 536 ms 54832 KB Output is correct
10 Correct 701 ms 52880 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 860 KB Output is correct
2 Correct 756 ms 18952 KB Output is correct
3 Correct 677 ms 19116 KB Output is correct
4 Correct 722 ms 19028 KB Output is correct
5 Correct 697 ms 19320 KB Output is correct
6 Correct 411 ms 19024 KB Output is correct
7 Correct 628 ms 19052 KB Output is correct
8 Correct 702 ms 19280 KB Output is correct
9 Correct 709 ms 19296 KB Output is correct
10 Correct 403 ms 19028 KB Output is correct
11 Correct 624 ms 19116 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 997 ms 170804 KB Output is correct
14 Correct 950 ms 172296 KB Output is correct
15 Correct 751 ms 168432 KB Output is correct
16 Correct 946 ms 191788 KB Output is correct
17 Correct 1014 ms 174324 KB Output is correct
18 Correct 707 ms 51464 KB Output is correct
19 Correct 456 ms 51812 KB Output is correct
20 Correct 536 ms 54832 KB Output is correct
21 Correct 701 ms 52880 KB Output is correct
22 Correct 2071 ms 177788 KB Output is correct
23 Correct 1797 ms 180740 KB Output is correct
24 Correct 1944 ms 181408 KB Output is correct
25 Correct 1975 ms 185208 KB Output is correct
26 Correct 1785 ms 180604 KB Output is correct
27 Correct 2013 ms 198116 KB Output is correct
28 Correct 1257 ms 178820 KB Output is correct
29 Correct 1701 ms 180544 KB Output is correct
30 Correct 1834 ms 180268 KB Output is correct
31 Correct 1804 ms 180420 KB Output is correct
32 Correct 1033 ms 58424 KB Output is correct
33 Correct 619 ms 53604 KB Output is correct
34 Correct 940 ms 49484 KB Output is correct
35 Correct 919 ms 49296 KB Output is correct
36 Correct 934 ms 49980 KB Output is correct
37 Correct 885 ms 49876 KB Output is correct