oj.uz

Submission #424475

# Submission time Handle Problem Language Result Execution time Memory
424475 2021-06-12T02:41:56 Z Osama_Alkhodairy Factories (JOI14_factories) C++17
15 / 100
 8000 ms 129996 KB 
#include <bits/stdc++.h>
#include "factories.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long

const int NN = 500001;
const int K = 20;
const ll INF = (ll)1e18;

int mark[NN], s[NN], e[NN], dep[NN], p[NN][K], dfstime;
ll d[NN], ans;
vector <pair <int, ll> > v[NN], g[NN];

void dfs(int node, int pnode){
    s[node] = dfstime++;
    p[node][0] = pnode;
    for(int i = 1 ; i < K ; i++){
        p[node][i] = p[p[node][i - 1]][i - 1];
    }
    for(auto &i : v[node]){
        if(i.first == pnode) continue;
        d[i.first] = d[node] + i.second;
        dep[i.first] = dep[node] + 1;
        dfs(i.first, node);
    }
    e[node] = dfstime - 1;
}
bool inside(int x, int y){
    return s[x] <= s[y] && e[y] <= e[x];
}
int lift(int x, int k){
    for(int i = 0 ; i < K ; i++){
        if((k >> i) & 1){
            x = p[x][i];
        }
    }
    return x;
}
int LCA(int x, int y){
    if(dep[x] >= dep[y]) swap(x, y);
    y = lift(y, dep[y] - dep[x]);
    if(x == y) return x;
    for(int i = 0 ; i < K ; i++){
        if(p[x][i] != p[y][i]){
            x = p[x][i];
            y = p[y][i];
        }
    }
    return p[x][0];
}
pair <ll, ll> solve(int node, int pnode){
    pair <ll, ll> cur = make_pair(INF, INF);
    if(mark[node] == 1) cur.first = 0;
    if(mark[node] == 2) cur.second = 0;
    for(auto &i : v[node]){
        if(i.first == pnode) continue;
        auto f = solve(i.first, node);
        f.first += i.second;
        f.second += i.second;
        ans = min(ans, cur.first + f.second);
        ans = min(ans, cur.second + f.first);
        cur.first = min(cur.first, f.first);
        cur.second = min(cur.second, f.second);
    }
    return cur;
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0 ; i < N - 1 ; i++){
        v[A[i]].push_back(make_pair(B[i], D[i]));
        v[B[i]].push_back(make_pair(A[i], D[i]));
    }
    dfs(0, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
    vector <int> all;
    for(int i = 0 ; i < S ; i++){
        mark[X[i]] = 1;
        all.push_back(X[i]);
    }
    for(int i = 0 ; i < T ; i++){
        mark[Y[i]] = 2;
        all.push_back(Y[i]);
    }
    sort(all.begin(), all.end(), [&](int l, int r){
        return s[l] < s[r];
    });
    int all_sz = all.size();
    for(int i = 0 ; i < all_sz ; i++){
        all.push_back(LCA(all[i], all[(i + 1) % all.size()]));
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    sort(all.begin(), all.end(), [&](int l, int r){
        return s[l] < s[r];
    });
    vector <int> cur;
    for(auto &i : all){
        while(cur.size() && !inside(cur.back(), i)) cur.pop_back();
        if(cur.size()){
            ll cost = d[i] - d[cur.back()];
            g[cur.back()].push_back(make_pair(i, cost));
            g[i].push_back(make_pair(cur.back(), cost));
        }
        cur.push_back(i);
    }
    ans = INF;
    solve(0, 0);
    for(auto &i : all){
        g[i].clear();
        mark[i] = 0;
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24140 KB Output is correct
2 Correct 1782 ms 42504 KB Output is correct
3 Correct 1922 ms 42556 KB Output is correct
4 Correct 1866 ms 42620 KB Output is correct
5 Correct 1728 ms 42584 KB Output is correct
6 Correct 1122 ms 42308 KB Output is correct
7 Correct 1963 ms 42556 KB Output is correct
8 Correct 1920 ms 42692 KB Output is correct
9 Correct 1738 ms 42604 KB Output is correct
10 Correct 1132 ms 42304 KB Output is correct
11 Correct 1945 ms 42460 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24012 KB Output is correct
2 Execution timed out 8096 ms 129996 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24140 KB Output is correct
2 Correct 1782 ms 42504 KB Output is correct
3 Correct 1922 ms 42556 KB Output is correct
4 Correct 1866 ms 42620 KB Output is correct
5 Correct 1728 ms 42584 KB Output is correct
6 Correct 1122 ms 42308 KB Output is correct
7 Correct 1963 ms 42556 KB Output is correct
8 Correct 1920 ms 42692 KB Output is correct
9 Correct 1738 ms 42604 KB Output is correct
10 Correct 1132 ms 42304 KB Output is correct
11 Correct 1945 ms 42460 KB Output is correct
12 Correct 20 ms 24012 KB Output is correct
13 Execution timed out 8096 ms 129996 KB Time limit exceeded
14 Halted 0 ms 0 KB -