Submission #1096992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096992		vjudge1	Factories (JOI14_factories)	C++17	100 / 100	2071 ms	198116 KiB

factories

#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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67