Submission #656368

#	Time	Username	Problem	Language	Result	Execution time	Memory
656368		HungAnhGoldIBO2020	Factories (JOI14_factories)	C++14	100 / 100	6712 ms	190052 KiB

factories

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
//#include "factories.h"
using namespace std;
const int N=500005;
const long long inf=1e14+7;
long long dp[N], dp1[N], dd[N];
vector<pair<int, long long>> g[N], c[N];
int vt[N], in[N], out[N], cc[N], h[N], p[N][21], t = 0;
bool cmp(int x, int y) {
    return in[x] < in[y];
}
void dfs(int u, int x) {
    t++;
    in[u] = t;
    p[u][0] = x;
    for (int i = 1; i <= 20; i++) {
        p[u][i] = p[p[u][i - 1]][i - 1];
    }
    for (auto w : g[u]) {
        int v = w.first, k = w.second;
        if (v != x) {
            h[v] = h[u] + 1;
            dd[v] = dd[u] + k;
            dfs(v, u);
        }
    }
    out[u] = t;
}
void compute_dp(int x){
    //cout<<x<<endl;
    if(vt[x]&1){
        dp[x]=0;
    }
    else{
        dp[x]=inf;
    }
    if(vt[x]&2){
        dp1[x]=0;
    }
    else{
        dp1[x]=inf;
    }
    for(int i=0;i<c[x].size();i++){
        compute_dp(c[x][i].first);
        dp[x]=min(dp[x],dp[c[x][i].first]+c[x][i].second);
        dp1[x]=min(dp1[x],dp1[c[x][i].first]+c[x][i].second);
        //cout<<x<<' '<<c[x][i].first<<' '<<dp[x]<<' '<<dp[c[x][i].first]+c[x][i].second<<' '<<dp1[x]<<' '<<dp1[c[x][i].first]+c[x][i].second<<endl;
    }
}
int LCA(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    int lg = log2(h[u]) + 1;
    for (int i = lg; i >= 0; i--) {
        if (h[p[u][i]] >= h[v]) {
            u = p[u][i];
        }
    }
    if (u == v) return u;
    for (int i = lg; i >= 0; i--) {
        if (p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}
long long trya(int u, int v) {
    return dd[u] + dd[v] - dd[LCA(u, v)] * 2;
}
bool check(int x, int y) {
    return (in[x] <= in[y]) && (out[y] <= out[x]);
}
void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
}
long long Query(int s, int x[], int t, int y[]) {
    vector<int> v;
    for (int i = 0; i < s; i++) {
        v.push_back(x[i]);
        vt[x[i]]++;
    }
    for (int i = 0; i < t; i++) {
        v.push_back(y[i]);
        vt[y[i]] += 2;
    }
    sort(v.begin(), v.end(), cmp);
    int k = v.size();
    for (int i = 1; i < k; i++) {
        int g = LCA(v[i], v[i - 1]);
        v.push_back(g);
    }
    sort(v.begin(), v.end(), cmp);
    v.erase(unique(v.begin(),v.end()),v.end());   //xoa di tat ca phan tu trung lap cua v
    for(int i=1;i<v.size();i++){
        int par=LCA(v[i],v[i-1]);
        c[par].push_back({v[i],trya(par,v[i])});
        //cout<<par<<' '<<v[i]<<' '<<trya(par,v[i])<<endl;
    }
    //cout<<"KEKW"<<endl;
    /*
    vector<int> st;
    //cout<<in[0]<<' '<<in[1]<<endl;
    for (int i = 0; i < v.size(); i++) {
        if (cc[v[i]] == 0) {
            while (st.size() && (!check(st.back(), v[i]))) {
                st.pop_back();
            }
            if (st.size()) {
                c[st.back()].push_back({v[i], trya(st.back(), v[i])});
                //cout<<st.back()<<' '<<v[i]<<' '<<trya(st.back(), v[i])<<endl;
            }
            st.push_back(v[i]);
            cc[v[i]] = 1;
        }
    }
    */
    long long res = inf;
    compute_dp(v[0]);
    for (int i = 0; i < v.size(); i++) {
        res=min(res,dp[v[i]]+dp1[v[i]]);
        //cout<<v[i]<<' '<<dp[v[i]]<<' '<<dp1[v[i]]<<" dp value"<<endl;
    }
    for (int i = 0; i < v.size(); i++) {
        cc[v[i]] = 0;
        c[v[i]].clear();
        vt[v[i]] = 0;
    }
    return res;
}
/*
signed main(){
    int a[]={0,1,2,2,4,1},b[]={1,2,3,4,5,6},d[]={4,4,5,6,5,3};
    Init(7,a,b,d);
    int e[]={0,6},f[]={3,4};
    cout<<Query(2,e,2,f)<<endl;
    int g[]={0,1,3},h[]={4,6};
    cout<<Query(3,g,2,h)<<endl;
    int i[]={2},j[]={5};
    cout<<Query(1,i,1,j)<<endl;
}
*/

Compilation message (stderr)

factories.cpp: In function 'void compute_dp(int)':
factories.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<c[x].size();i++){
      |                 ~^~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=1;i<v.size();i++){
      |                 ~^~~~~~~~~
factories.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
factories.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67