oj.uz

Submission #673993

# Submission time Handle Problem Language Result Execution time Memory
673993 2022-12-22T13:49:57 Z Cookie Factories (JOI14_factories) C++14
100 / 100
 4361 ms 194004 KB 
#include<bits/stdc++.h>

#include<fstream>
//#include "factories.h"

using namespace std;
ifstream fin("INTERNET.INP");
ofstream fout("INTERNET.OUT");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>

const int mxn = 5e5, sq = 300, mxv = 1e4;


int n;
vt<pll>adj[mxn + 1];
int id[mxn + 1];
ll sz[mxn + 1], par[mxn + 1], ans[mxn + 1], tt = 0, l[mxn + 1];
vt<int>s, t;
ll dis[21][mxn + 1];
// map will TLE need to use this
bool vis[mxn + 1];
int dfs(int s, int pre){
    sz[s] = 1;
    for(auto [i, w]: adj[s]){
        if(i != pre && !vis[i]){
            sz[s] += dfs(i, s);
        }
    }
    return(sz[s]);
}
int centroid(int s, int pre, int need){
    for(auto [i, w]: adj[s]){
        if(i != pre && !vis[i]){
            if(sz[i] * 2 > need)return(centroid(i, s, need));
        }
    }
    return(s);
}
void dfs2(int s, int step, int pre, ll d){
    dis[step][s] = d;
    for(auto [i, w]: adj[s]){
        if(i != pre && !vis[i]){
            dfs2(i, step, s, d + w);
        }
    }
}
void build(int s, int pre, int step){
    int c = centroid(s, -1, dfs(s, -1));
    vis[c] = true; par[c] = pre; id[c] = tt++;
    dis[step][c] = 0;  l[c] = step;
    for(auto [i, w]: adj[c]){
        if(i != pre && !vis[i]){
            dfs2(i, step,  c, w);
        }
    }
    for(auto [i, w]: adj[c]){
        if(!vis[i]){
            build(i, c, step + 1);
        }
    }
}
void Init(int N, int A[], int B[], int D[]) {

    n = N;
    for(int i = 0; i < n - 1; i++){
        adj[A[i]].pb({B[i], D[i]}); adj[B[i]].pb({A[i], D[i]});
    }
    build(0, -1, 0); //centroid decompsoing the tree
    for(int i = 0; i < n; i++)ans[i] = 1e18;
}
void add(int x){
    int le = l[x];
    for(int i = x; i != -1; i = par[i]){
        ans[i] = min(ans[i], dis[le][x]); le--;
    }
}
void rem(int x){
    for(int i = x; i != -1; i = par[i])ans[i] = 1e18;
}
ll see(int x){
    ll res = 1e18; int le = l[x];
    
    for(int i = x; i != -1; i = par[i]){
        res = min(res, ans[i] + dis[le][x]); le--;
    }
   
    return(res);
}
ll solve(){
    for(int i = 0; i < s.size(); i++)add(s[i]);
    ll res = 1e18;
    for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
    
    for(int i = 0; i < s.size(); i++)rem(s[i]);
    return(res);
}
long long Query(int S, int X[], int T, int Y[]) {
    s.clear(); t.clear();
    for(int i = 0; i < S; i++)s.pb(X[i]);
    for(int i = 0; i < T; i++)t.pb(Y[i]);
    
    return(solve());
 
}

Compilation message

factories.cpp: In function 'int dfs(int, int)':
factories.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for(auto [i, w]: adj[s]){
      |              ^
factories.cpp: In function 'int centroid(int, int, int)':
factories.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for(auto [i, w]: adj[s]){
      |              ^
factories.cpp: In function 'void dfs2(int, int, int, long long int)':
factories.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto [i, w]: adj[s]){
      |              ^
factories.cpp: In function 'void build(int, int, int)':
factories.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [i, w]: adj[c]){
      |              ^
factories.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     for(auto [i, w]: adj[c]){
      |              ^
factories.cpp: In function 'long long int solve()':
factories.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i = 0; i < s.size(); i++)add(s[i]);
      |                    ~~^~~~~~~~~~
factories.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
      |                    ~~^~~~~~~~~~
factories.cpp:102:22: 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 = 0; i < s.size(); i++)rem(s[i]);
      |                    ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12500 KB Output is correct
2 Correct 276 ms 21052 KB Output is correct
3 Correct 308 ms 21160 KB Output is correct
4 Correct 300 ms 21320 KB Output is correct
5 Correct 328 ms 21472 KB Output is correct
6 Correct 204 ms 20628 KB Output is correct
7 Correct 293 ms 21116 KB Output is correct
8 Correct 302 ms 21196 KB Output is correct
9 Correct 319 ms 21468 KB Output is correct
10 Correct 211 ms 20620 KB Output is correct
11 Correct 295 ms 21104 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 1766 ms 127600 KB Output is correct
3 Correct 2737 ms 163812 KB Output is correct
4 Correct 699 ms 92464 KB Output is correct
5 Correct 3926 ms 189244 KB Output is correct
6 Correct 2996 ms 165896 KB Output is correct
7 Correct 1006 ms 59188 KB Output is correct
8 Correct 369 ms 47288 KB Output is correct
9 Correct 1107 ms 63352 KB Output is correct
10 Correct 909 ms 60676 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12500 KB Output is correct
2 Correct 276 ms 21052 KB Output is correct
3 Correct 308 ms 21160 KB Output is correct
4 Correct 300 ms 21320 KB Output is correct
5 Correct 328 ms 21472 KB Output is correct
6 Correct 204 ms 20628 KB Output is correct
7 Correct 293 ms 21116 KB Output is correct
8 Correct 302 ms 21196 KB Output is correct
9 Correct 319 ms 21468 KB Output is correct
10 Correct 211 ms 20620 KB Output is correct
11 Correct 295 ms 21104 KB Output is correct
12 Correct 9 ms 12244 KB Output is correct
13 Correct 1766 ms 127600 KB Output is correct
14 Correct 2737 ms 163812 KB Output is correct
15 Correct 699 ms 92464 KB Output is correct
16 Correct 3926 ms 189244 KB Output is correct
17 Correct 2996 ms 165896 KB Output is correct
18 Correct 1006 ms 59188 KB Output is correct
19 Correct 369 ms 47288 KB Output is correct
20 Correct 1107 ms 63352 KB Output is correct
21 Correct 909 ms 60676 KB Output is correct
22 Correct 2286 ms 152900 KB Output is correct
23 Correct 2295 ms 157620 KB Output is correct
24 Correct 3594 ms 172772 KB Output is correct
25 Correct 3440 ms 176440 KB Output is correct
26 Correct 3395 ms 172200 KB Output is correct
27 Correct 4361 ms 194004 KB Output is correct
28 Correct 786 ms 103280 KB Output is correct
29 Correct 3359 ms 172128 KB Output is correct
30 Correct 3377 ms 171356 KB Output is correct
31 Correct 3294 ms 171904 KB Output is correct
32 Correct 1060 ms 64808 KB Output is correct
33 Correct 327 ms 48532 KB Output is correct
34 Correct 639 ms 54268 KB Output is correct
35 Correct 649 ms 54280 KB Output is correct
36 Correct 853 ms 57504 KB Output is correct
37 Correct 880 ms 57600 KB Output is correct