oj.uz

Submission #673976

# Submission time Handle Problem Language Result Execution time Memory
673976 2022-12-22T13:31:38 Z Cookie Factories (JOI14_factories) C++14
15 / 100
 8000 ms 411432 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];
ll sz[mxn + 1], par[mxn + 1], ans[mxn + 1];
vt<int>s, t;
map<int, ll>dis[mxn + 1];
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 c, int pre, ll d){
    dis[c][s] = d;
    for(auto [i, w]: adj[s]){
        if(i != pre && !vis[i]){
            dfs2(i, c, s, d + w);
        }
    }
}
void build(int s, int pre){
    int c = centroid(s, -1, dfs(s, -1));
    vis[c] = true; par[c] = pre;
    dis[c][c] = 0;
    for(auto [i, w]: adj[c]){
        if(i != pre && !vis[i]){
            dfs2(i, c,  c, w);
        }
    }
    for(auto [i, w]: adj[c]){
        if(!vis[i]){
            build(i, c);
        }
    }
}
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); //centroid decompsoing the tree
    for(int i = 0; i < n; i++)ans[i] = 1e18;
}
void add(int x){
    for(int i = x; i != -1; i = par[i])ans[i] = min(ans[i], dis[i][x]);
}
void rem(int x){
    for(int i = x; i != -1; i = par[i])ans[i] = 1e18;
}
ll see(int x){
    ll res = 1e18; int cnt = 0;
    for(int i = x; i != -1; i = par[i]){
        cnt++; res = min(res, ans[i] + dis[i][x]);
    }
    assert(cnt <= 100);
    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:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [i, w]: adj[s]){
      |              ^
factories.cpp: In function 'int centroid(int, int, int)':
factories.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for(auto [i, w]: adj[s]){
      |              ^
factories.cpp: In function 'void dfs2(int, int, int, long long int)':
factories.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto [i, w]: adj[s]){
      |              ^
factories.cpp: In function 'void build(int, int)':
factories.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [i, w]: adj[c]){
      |              ^
factories.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for(auto [i, w]: adj[c]){
      |              ^
factories.cpp: In function 'long long int solve()':
factories.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 0; i < s.size(); i++)add(s[i]);
      |                    ~~^~~~~~~~~~
factories.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
      |                    ~~^~~~~~~~~~
factories.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     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 32 ms 36180 KB Output is correct
2 Correct 1462 ms 46288 KB Output is correct
3 Correct 2370 ms 47296 KB Output is correct
4 Correct 2207 ms 47324 KB Output is correct
5 Correct 2884 ms 48028 KB Output is correct
6 Correct 431 ms 44820 KB Output is correct
7 Correct 2508 ms 47120 KB Output is correct
8 Correct 2169 ms 47436 KB Output is correct
9 Correct 2648 ms 47992 KB Output is correct
10 Correct 405 ms 44792 KB Output is correct
11 Correct 2216 ms 47192 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35796 KB Output is correct
2 Execution timed out 8025 ms 411432 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 36180 KB Output is correct
2 Correct 1462 ms 46288 KB Output is correct
3 Correct 2370 ms 47296 KB Output is correct
4 Correct 2207 ms 47324 KB Output is correct
5 Correct 2884 ms 48028 KB Output is correct
6 Correct 431 ms 44820 KB Output is correct
7 Correct 2508 ms 47120 KB Output is correct
8 Correct 2169 ms 47436 KB Output is correct
9 Correct 2648 ms 47992 KB Output is correct
10 Correct 405 ms 44792 KB Output is correct
11 Correct 2216 ms 47192 KB Output is correct
12 Correct 21 ms 35796 KB Output is correct
13 Execution timed out 8025 ms 411432 KB Time limit exceeded
14 Halted 0 ms 0 KB -