oj.uz

답안 #656679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656679 2022-11-08T03:39:36 Z minhcool 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 184740 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];
//dist[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;
        //dist[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];
            //dist[j][i] = dist[j][i - 1] + dist[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 temp2 = dist(temp, xx);
            for(int i = 19; i >= 0; i--){
                int x = anc[temp3][i];
                if(!x) continue;
                if(dist(u, x) < dist(temp, x)) temp3 = x;
                //if((temp2 + (d2[x] - d[xx])) > (d2[u] - d2[x])) temp3 = x;
            }
        }
        assert(d2[u] >= d2[temp] || temp3 == 1);
        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:145:16: warning: unused variable 'temp2' [-Wunused-variable]
  145 |             ll temp2 = dist(temp, xx);
      |                ^~~~~
factories.cpp:170: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]
  170 |         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:179: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]
  179 |         assert(temp < nodes.size());
      |                ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 12556 KB Output is correct
2 Correct 1539 ms 21808 KB Output is correct
3 Correct 2153 ms 21644 KB Output is correct
4 Correct 1979 ms 22720 KB Output is correct
5 Correct 2768 ms 22480 KB Output is correct
6 Correct 1229 ms 21832 KB Output is correct
7 Correct 2118 ms 21584 KB Output is correct
8 Correct 2162 ms 21688 KB Output is correct
9 Correct 2544 ms 22364 KB Output is correct
10 Correct 1049 ms 21832 KB Output is correct
11 Correct 2033 ms 21792 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 12352 KB Output is correct
2 Correct 2221 ms 150424 KB Output is correct
3 Correct 6396 ms 154400 KB Output is correct
4 Correct 1435 ms 148144 KB Output is correct
5 Correct 7879 ms 184740 KB Output is correct
6 Correct 6403 ms 155708 KB Output is correct
7 Correct 5545 ms 48824 KB Output is correct
8 Correct 1728 ms 48588 KB Output is correct
9 Execution timed out 8055 ms 52096 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 12556 KB Output is correct
2 Correct 1539 ms 21808 KB Output is correct
3 Correct 2153 ms 21644 KB Output is correct
4 Correct 1979 ms 22720 KB Output is correct
5 Correct 2768 ms 22480 KB Output is correct
6 Correct 1229 ms 21832 KB Output is correct
7 Correct 2118 ms 21584 KB Output is correct
8 Correct 2162 ms 21688 KB Output is correct
9 Correct 2544 ms 22364 KB Output is correct
10 Correct 1049 ms 21832 KB Output is correct
11 Correct 2033 ms 21792 KB Output is correct
12 Correct 10 ms 12352 KB Output is correct
13 Correct 2221 ms 150424 KB Output is correct
14 Correct 6396 ms 154400 KB Output is correct
15 Correct 1435 ms 148144 KB Output is correct
16 Correct 7879 ms 184740 KB Output is correct
17 Correct 6403 ms 155708 KB Output is correct
18 Correct 5545 ms 48824 KB Output is correct
19 Correct 1728 ms 48588 KB Output is correct
20 Execution timed out 8055 ms 52096 KB Time limit exceeded
21 Halted 0 ms 0 KB -