답안 #656686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656686 2022-11-08T03:44:50 Z minhcool 공장들 (JOI14_factories) C++17
15 / 100
8000 ms 263244 KB
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const ll N = 5e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;
 
ll n;
vector<pair<ll, ll>> Adj[N];
 
ll d1[N], d2[N];
 
ll anc[N][20];
ll dis[N][20];
 
void dfs(int u, int p){
    for(auto it : Adj[u]){
        int v = it.fi, w = it.se;
        if(v == p) continue;
        d1[v] = d1[u] + 1;
        d2[v] = d2[u] + w;
        anc[v][0] = u;
        dis[v][0] = w;
        dfs(v, u);
    }
}
 
void prep(){
    for(int i = 1; i <= 19; i++){
        for(int j = 1; j <= n; j++){
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
            dis[j][i] = dis[j][i - 1] + dis[anc[j][i - 1]][i - 1];
        }
    }
}
 
int lca(int x, int y){
    if(d1[x] > d1[y]) swap(x, y);
    for(int i = 19; i >= 0; i--){
        if((d1[x] + (1LL << i)) <= d1[y]) y = anc[y][i];
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--){
        if(anc[x][i] != anc[y][i]){
            x = anc[x][i], y = anc[y][i];
        }
    }
    return anc[x][0];
}
 
ll dist(int x, int y){
    return d2[x] + d2[y] - 2 * d2[lca(x, y)];
}
 
int cnt;
int pos[N], l[N], r[N];
int arr[N];
 
void pre_dfs(int u, int p){
    cnt++;
    pos[u] = l[u] = cnt;
    arr[cnt] = u;
    for(auto it : Adj[u]){
        int v = it.fi;
        if(v == p) continue;
        pre_dfs(v, u);
    }
    r[u] = cnt;
}
 
void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i = 0; i < (n - 1); i++){
        Adj[A[i] + 1].pb({B[i] + 1, D[i]});
        Adj[B[i] + 1].pb({A[i] + 1, D[i]});
    }
    pre_dfs(1, 1);
    dfs(1, 1);
    prep();
}
 
bool choose1[N], choose2[N];
 
int IT[N << 2];
 
vector<int> vis;
 
void upd(int id, int l, int r, int L, int R, int val){
    vis.pb(id);
    if(l > R || r < L) return;
    if(l >= L && r <= R){
        IT[id] = val;
        return;
    }
    if(IT[id]){
        IT[id << 1] = IT[id << 1 | 1] = IT[id];
        IT[id] = 0;
    }
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, L, R, val);
    upd(id << 1 | 1, mid + 1, r, L, R, val);
}
 
int get(int id, int l, int r, int pos){
    vis.pb(id);
    if(l == r){
        return IT[id];
    }
    if(IT[id]){
        IT[id << 1] = IT[id << 1 | 1] = IT[id];
        IT[id] = 0;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) return get(id << 1, l, mid, pos);
    else return get(id << 1 | 1, mid + 1, r, pos);
}
 
int sub[N];
 
 
ll Query(int S, int X[], int T, int Y[]){
    vis.clear();
    // build the subtree part
    vector<pair<ll, ll>> nodes;
    for(int i = 0; i < S; i++) nodes.pb({d2[X[i] + 1], X[i] + 1});
    sort(nodes.begin(), nodes.end());
    vector<pair<ll, ll>> queries;
    int cnt = -1;
    bool ck = 0;
    for(auto it : nodes){
        cnt++;
        ll u = it.se;
        ll temp = get(1, 1, n, pos[u]), temp3 = u;
        if(!cnt) temp3 = 1;
        else{
            ll xx = lca(temp, u);
            ll cur1 = dist(temp, u), cur2 = 0;
            if(d2[u] < d2[temp]) temp3 = 1;
            else{
            for(int i = 19; i >= 0; i--){
                int x = anc[temp3][i];
                if(!x) continue;
                //if(d2[x] < d2[xx]) continue;
                //if((cur1 - dis[temp3][i]) > (cur2 + dis[temp3][i])) temp3 = x;
                if(dist(u, x) < dist(temp, x)) temp3 = x;
                //if((temp2 + (d2[x] - d[xx])) > (d2[u] - d2[x])) temp3 = x;
            }
            }
        }
        //if(d2[u] >= d2[temp]) assert(d2[temp3] >= d2[lca(temp, u)]);
        //assert(d2[u] >= d2[temp]);
        sub[u] = temp3;
        upd(1, 1, n, l[temp3], r[temp3], u);
        if(temp3 == 1) ck = 1;
        queries.pb({l[temp3], cnt});
        queries.pb({r[temp3] + 1, cnt});
    }
    assert(ck);
    sort(queries.begin(), queries.end());
    set<ll> cur;
    // process part
    vector<ii> nodes2;
    for(int i = 0; i < T; i++) nodes2.pb({pos[Y[i] + 1], Y[i] + 1});
    sort(nodes2.begin(), nodes2.end());
    int itr = 0;
    ll answer = oo;
    for(auto it : nodes2){
        while(itr < queries.size() && queries[itr].fi <= it.fi){
            if(cur.find(queries[itr].se) != cur.end()) cur.erase(queries[itr].se);
            else cur.insert(queries[itr].se);
            itr++;
        }
        //assert(itr < queries.size());
        //assert(cur.size());
        //int temp = 1;
        int temp = (*cur.rbegin());
        assert(temp < nodes.size());
        answer = min(answer, dist(it.se, nodes[temp].se));
    }
    for(auto it : vis) IT[it] = 0;
    return answer;
    /*
    if(S <= 5000 && T <= 5000){
        ll ans = oo;
        for(int i = 0; i < S; i++){
            for(int j = 0; j < T; j++) ans = min(ans, dist(X[i] + 1, Y[j] + 1));
        }
        return ans;
    }
    else{
        answer = oo;
        //vis.clear();
        for(int i = 0; i < S; i++) choose1[X[i] + 1] = 1;
        for(int i = 0; i < T; i++) choose2[Y[i] + 1] = 1;
        ini(1, 1, n);
        main_dfs(1, 1);
        for(int i = 0; i < S; i++) choose1[X[i] + 1] = 0;
        for(int i = 0; i < T; i++) choose2[Y[i] + 1] = 0;
        return answer;
        //vis.clear();
    }*/
 
}
 
/*
void process(){
    int n, q;
    vector<int> a(n - 1), b(n - 1), d(n - 1);
    cin >> n >> q;
    for(int i = 0; i < (n - 1); i++){
        cin >> a[i] >> b[i] >> d[i];
    }
    Init(n, a, b, d);
    while(q--){
        int sz1, sz2;
        vector<int> vc1, vc2;
        cin >> sz1 >> sz2;
        vc1.resize(sz1);
        for(int i = 0; i < sz1; i++) cin >> vc1[i];
        vc2.resize(sz2);
        for(int i = 0; i < sz2; i++) cin >> vc2[i];
        cout << Query(sz1, vc1, sz2, vc2) << "\n"; 
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    process();
}*/

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:144:16: warning: unused variable 'xx' [-Wunused-variable]
  144 |             ll xx = lca(temp, u);
      |                ^~
factories.cpp:145:16: warning: unused variable 'cur1' [-Wunused-variable]
  145 |             ll cur1 = dist(temp, u), cur2 = 0;
      |                ^~~~
factories.cpp:145:38: warning: unused variable 'cur2' [-Wunused-variable]
  145 |             ll cur1 = dist(temp, u), cur2 = 0;
      |                                      ^~~~
factories.cpp:176:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         while(itr < queries.size() && queries[itr].fi <= it.fi){
      |               ~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from factories.cpp:1:
factories.cpp:185:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |         assert(temp < nodes.size());
      |                ~~~~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 12624 KB Output is correct
2 Correct 1425 ms 22824 KB Output is correct
3 Correct 2013 ms 22468 KB Output is correct
4 Correct 1795 ms 23484 KB Output is correct
5 Correct 2362 ms 23180 KB Output is correct
6 Correct 1026 ms 22760 KB Output is correct
7 Correct 1970 ms 22676 KB Output is correct
8 Correct 1934 ms 22844 KB Output is correct
9 Correct 2339 ms 23112 KB Output is correct
10 Correct 1042 ms 22640 KB Output is correct
11 Correct 2054 ms 22568 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 12372 KB Output is correct
2 Correct 2458 ms 228768 KB Output is correct
3 Correct 6645 ms 232660 KB Output is correct
4 Correct 1511 ms 226452 KB Output is correct
5 Execution timed out 8064 ms 263244 KB Time limit exceeded
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 12624 KB Output is correct
2 Correct 1425 ms 22824 KB Output is correct
3 Correct 2013 ms 22468 KB Output is correct
4 Correct 1795 ms 23484 KB Output is correct
5 Correct 2362 ms 23180 KB Output is correct
6 Correct 1026 ms 22760 KB Output is correct
7 Correct 1970 ms 22676 KB Output is correct
8 Correct 1934 ms 22844 KB Output is correct
9 Correct 2339 ms 23112 KB Output is correct
10 Correct 1042 ms 22640 KB Output is correct
11 Correct 2054 ms 22568 KB Output is correct
12 Correct 10 ms 12372 KB Output is correct
13 Correct 2458 ms 228768 KB Output is correct
14 Correct 6645 ms 232660 KB Output is correct
15 Correct 1511 ms 226452 KB Output is correct
16 Execution timed out 8064 ms 263244 KB Time limit exceeded
17 Halted 0 ms 0 KB -