oj.uz

Submission #656368

# Submission time Handle Problem Language Result Execution time Memory
656368 2022-11-07T05:08:06 Z HungAnhGoldIBO2020 Factories (JOI14_factories) C++14
100 / 100
 6712 ms 190052 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24148 KB Output is correct
2 Correct 1109 ms 32928 KB Output is correct
3 Correct 1364 ms 33024 KB Output is correct
4 Correct 1369 ms 33120 KB Output is correct
5 Correct 1216 ms 33328 KB Output is correct
6 Correct 652 ms 32960 KB Output is correct
7 Correct 1399 ms 33120 KB Output is correct
8 Correct 1305 ms 33168 KB Output is correct
9 Correct 1219 ms 33236 KB Output is correct
10 Correct 655 ms 32848 KB Output is correct
11 Correct 1366 ms 33108 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 1736 ms 124968 KB Output is correct
3 Correct 3776 ms 147232 KB Output is correct
4 Correct 1062 ms 141084 KB Output is correct
5 Correct 3076 ms 182456 KB Output is correct
6 Correct 3910 ms 149472 KB Output is correct
7 Correct 3196 ms 67336 KB Output is correct
8 Correct 861 ms 66496 KB Output is correct
9 Correct 2571 ms 73428 KB Output is correct
10 Correct 3111 ms 68564 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24148 KB Output is correct
2 Correct 1109 ms 32928 KB Output is correct
3 Correct 1364 ms 33024 KB Output is correct
4 Correct 1369 ms 33120 KB Output is correct
5 Correct 1216 ms 33328 KB Output is correct
6 Correct 652 ms 32960 KB Output is correct
7 Correct 1399 ms 33120 KB Output is correct
8 Correct 1305 ms 33168 KB Output is correct
9 Correct 1219 ms 33236 KB Output is correct
10 Correct 655 ms 32848 KB Output is correct
11 Correct 1366 ms 33108 KB Output is correct
12 Correct 14 ms 24020 KB Output is correct
13 Correct 1736 ms 124968 KB Output is correct
14 Correct 3776 ms 147232 KB Output is correct
15 Correct 1062 ms 141084 KB Output is correct
16 Correct 3076 ms 182456 KB Output is correct
17 Correct 3910 ms 149472 KB Output is correct
18 Correct 3196 ms 67336 KB Output is correct
19 Correct 861 ms 66496 KB Output is correct
20 Correct 2571 ms 73428 KB Output is correct
21 Correct 3111 ms 68564 KB Output is correct
22 Correct 3519 ms 160116 KB Output is correct
23 Correct 3161 ms 161092 KB Output is correct
24 Correct 4970 ms 164844 KB Output is correct
25 Correct 5233 ms 167364 KB Output is correct
26 Correct 6712 ms 157660 KB Output is correct
27 Correct 5079 ms 190052 KB Output is correct
28 Correct 1793 ms 155812 KB Output is correct
29 Correct 6464 ms 156336 KB Output is correct
30 Correct 6562 ms 155752 KB Output is correct
31 Correct 6475 ms 156252 KB Output is correct
32 Correct 2669 ms 75420 KB Output is correct
33 Correct 1109 ms 70052 KB Output is correct
34 Correct 2025 ms 65848 KB Output is correct
35 Correct 1892 ms 65640 KB Output is correct
36 Correct 3098 ms 66604 KB Output is correct
37 Correct 3219 ms 66432 KB Output is correct