oj.uz

답안 #673973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673973 2022-12-22T13:27:16 Z Cookie 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 411008 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]){
            dfs(i, s); sz[s] += sz[i];
        }
    }
    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;
    for(int i = x; i != -1; i = par[i])res = min(res, ans[i] + dis[i][x]);
    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:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < s.size(); i++)add(s[i]);
      |                    ~~^~~~~~~~~~
factories.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
      |                    ~~^~~~~~~~~~
factories.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i = 0; i < s.size(); i++)rem(s[i]);
      |                    ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 35924 KB Output is correct
2 Correct 1438 ms 46164 KB Output is correct
3 Correct 2176 ms 47020 KB Output is correct
4 Correct 2131 ms 46940 KB Output is correct
5 Correct 2676 ms 47832 KB Output is correct
6 Correct 441 ms 44620 KB Output is correct
7 Correct 2125 ms 46976 KB Output is correct
8 Correct 2157 ms 47068 KB Output is correct
9 Correct 2638 ms 47860 KB Output is correct
10 Correct 442 ms 44632 KB Output is correct
11 Correct 2198 ms 46976 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35824 KB Output is correct
2 Execution timed out 8109 ms 411008 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 35924 KB Output is correct
2 Correct 1438 ms 46164 KB Output is correct
3 Correct 2176 ms 47020 KB Output is correct
4 Correct 2131 ms 46940 KB Output is correct
5 Correct 2676 ms 47832 KB Output is correct
6 Correct 441 ms 44620 KB Output is correct
7 Correct 2125 ms 46976 KB Output is correct
8 Correct 2157 ms 47068 KB Output is correct
9 Correct 2638 ms 47860 KB Output is correct
10 Correct 442 ms 44632 KB Output is correct
11 Correct 2198 ms 46976 KB Output is correct
12 Correct 21 ms 35824 KB Output is correct
13 Execution timed out 8109 ms 411008 KB Time limit exceeded
14 Halted 0 ms 0 KB -