oj.uz

Submission #656678

# Submission time Handle Problem Language Result Execution time Memory
656678 2022-11-08T03:26:24 Z minhcool Factories (JOI14_factories) C++17
33 / 100
 8000 ms 193816 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]);
        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

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12500 KB Output is correct
2 Correct 1416 ms 25096 KB Output is correct
3 Correct 1938 ms 22356 KB Output is correct
4 Correct 1697 ms 23620 KB Output is correct
5 Correct 2205 ms 22536 KB Output is correct
6 Correct 1010 ms 22220 KB Output is correct
7 Correct 1904 ms 22100 KB Output is correct
8 Correct 1861 ms 22256 KB Output is correct
9 Correct 2225 ms 22996 KB Output is correct
10 Correct 1027 ms 22468 KB Output is correct
11 Correct 1911 ms 22220 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12244 KB Output is correct
2 Correct 2147 ms 150988 KB Output is correct
3 Correct 6131 ms 155112 KB Output is correct
4 Correct 1403 ms 148828 KB Output is correct
5 Correct 7669 ms 185508 KB Output is correct
6 Correct 6210 ms 156256 KB Output is correct
7 Correct 5107 ms 50116 KB Output is correct
8 Correct 1459 ms 49796 KB Output is correct
9 Correct 7970 ms 55036 KB Output is correct
10 Correct 5005 ms 51632 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12500 KB Output is correct
2 Correct 1416 ms 25096 KB Output is correct
3 Correct 1938 ms 22356 KB Output is correct
4 Correct 1697 ms 23620 KB Output is correct
5 Correct 2205 ms 22536 KB Output is correct
6 Correct 1010 ms 22220 KB Output is correct
7 Correct 1904 ms 22100 KB Output is correct
8 Correct 1861 ms 22256 KB Output is correct
9 Correct 2225 ms 22996 KB Output is correct
10 Correct 1027 ms 22468 KB Output is correct
11 Correct 1911 ms 22220 KB Output is correct
12 Correct 10 ms 12244 KB Output is correct
13 Correct 2147 ms 150988 KB Output is correct
14 Correct 6131 ms 155112 KB Output is correct
15 Correct 1403 ms 148828 KB Output is correct
16 Correct 7669 ms 185508 KB Output is correct
17 Correct 6210 ms 156256 KB Output is correct
18 Correct 5107 ms 50116 KB Output is correct
19 Correct 1459 ms 49796 KB Output is correct
20 Correct 7970 ms 55036 KB Output is correct
21 Correct 5005 ms 51632 KB Output is correct
22 Correct 3567 ms 172932 KB Output is correct
23 Correct 3437 ms 193816 KB Output is correct
24 Correct 6182 ms 175064 KB Output is correct
25 Correct 6779 ms 177924 KB Output is correct
26 Execution timed out 8068 ms 157100 KB Time limit exceeded
27 Halted 0 ms 0 KB -