oj.uz

Submission #841829

# Submission time Handle Problem Language Result Execution time Memory
841829 2023-09-02T07:06:40 Z eltu0815 Two Currencies (JOI23_currencies) C++14
30 / 100
 1460 ms 47904 KB 
#include <bits/stdc++.h>
#define MAX 100005
#define MOD 998244353
#define INF (ll)(1e18)
#define inf (1987654321)

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef complex<long double> cpx;
constexpr long double PI = acos(-1);

int tt, n, m, k, q;

int in[MAX], out[MAX], dep[MAX];
int parent[MAX][20];
int lo[MAX], hi[MAX];
int ans[MAX];

vector<pii> edge;
vector<pii> chkpoint;
vector<pair<pii, pll> > inp;

vector<int> graph[MAX];
vector<int> event[MAX];

ll seg[MAX << 2];
void init(int str, int ed, int node) {
    seg[node] = 0;
    if(str == ed) return;
    int mid = str + ed >> 1;
    init(str, mid, node << 1);
    init(mid + 1, ed, node << 1 | 1);
}

void update(int str, int ed, int left, int right, ll val, int node) {
    if(str > right || ed < left) return;
    if(left <= str && ed <= right) {
        seg[node] += val;
        return;
    }
    int mid = str + ed >> 1;
    update(str, mid, left, right, val, node << 1);
    update(mid + 1, ed, left, right, val, node << 1 | 1);
}

ll query(int str, int ed, int idx, int node) {
    if(str == ed) return seg[node];
    int mid = str + ed >> 1;
    if(idx <= mid) return query(str, mid, idx, node << 1) + seg[node];
    else return query(mid + 1, ed, idx, node << 1 | 1) + seg[node];
}

int pv = 0;
void dfs(int node, int par) {
    parent[node][0] = par; in[node] = ++pv;
    for(auto v : graph[node]) {
        if(v == par) continue;
        dep[v] = dep[node] + 1;
        dfs(v, node);
    }
    out[node] = pv;
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    int diff = dep[a] - dep[b], j = 0;
    while(diff) {
        if(diff & 1) a = parent[a][j];
        diff >>= 1; ++j;
    }
    if(a == b) return a;
    for(int i = 19; i >= 0; --i) {
        if(parent[a][i] == parent[b][i]) continue;
        a = parent[a][i];
        b = parent[b][i];
    }
    return parent[a][0];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m >> q;
    edge.resize(n - 1);
    for(int i = 0; i < n - 1; ++i) {
        int a, b; cin >> a >> b;
        edge[i] = {a, b};
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    chkpoint.resize(m);
    for(int i = 0; i < m; ++i) cin >> chkpoint[i].second >> chkpoint[i].first;
    for(int i = 0; i < m; ++i) chkpoint[i].second--;
    sort(chkpoint.begin(), chkpoint.end());
    
    inp.resize(q);
    for(int i = 0; i < q; ++i) cin >> inp[i].first.first >> inp[i].first.second >> inp[i].second.first >> inp[i].second.second;
    for(int i = 0; i < q; ++i) lo[i] = -1, hi[i] = m;
    
    dfs(1, 0);
    for(int i = 1; i <= n; ++i) for(int j = 1; j < 20; ++j) parent[i][j] = parent[parent[i][j - 1]][j - 1];
    
    while(true) {
        int flag = 1;
        for(int i = 0; i < m; ++i) event[i].clear();
        for(int i = 0; i < q; ++i) {
            if(lo[i] + 1 == hi[i]) continue;
            flag = 0;
            int mid = lo[i] + hi[i] >> 1;
            event[mid].push_back(i);
        }
        
        if(flag) break;
        
        init(1, n, 1);
        for(int i = 0; i < m; ++i) {
            int j = chkpoint[i].second;
            int u = edge[j].first, v = edge[j].second;
            if(dep[u] < dep[v]) swap(u, v);
            update(1, n, in[u], out[u], chkpoint[i].first, 1);
            
            for(auto k : event[i]) {
                int a = inp[k].first.first, b = inp[k].first.second;
                int p = lca(a, b);
                ll sum = query(1, n, in[a], 1);
                sum += query(1, n, in[b], 1);
                sum -= 2 * query(1, n, in[p], 1);
                
                if(sum <= inp[k].second.second) lo[k] = i;
                else hi[k] = i;
            }
        }
    }
    
    for(int i = 0; i < m; ++i) event[i].clear();
    for(int i = 0; i < q; ++i) {
        if(lo[i] == -1) continue;
        event[lo[i]].push_back(i);
    }
    
    init(1, n, 1);
    for(int i = m - 1; i >= 0; --i) {
        for(auto k : event[i]) {
            int a = inp[k].first.first, b = inp[k].first.second;
            int p = lca(a, b);
            ll sum = query(1, n, in[a], 1);
            sum += query(1, n, in[b], 1);
            sum -= 2 * query(1, n, in[p], 1);
            
            if(sum <= inp[k].second.first) ans[k] = inp[k].second.first - sum;
            else ans[k] = -1;
        }
        int j = chkpoint[i].second;
        int u = edge[j].first, v = edge[j].second;
        if(dep[u] < dep[v]) swap(u, v);
        update(1, n, in[u], out[u], 1, 1);
    }
    
    for(int i = 0; i < q; ++i) {
        if(lo[i] != -1) continue;
        
        int a = inp[i].first.first, b = inp[i].first.second;
        int p = lca(a, b);
        ll sum = query(1, n, in[a], 1);
        sum += query(1, n, in[b], 1);
        sum -= 2 * query(1, n, in[p], 1);
        
        if(sum <= inp[i].second.first) ans[i] = inp[i].second.first - sum;
        else ans[i] = -1;
    }
    
    for(int i = 0; i < q; ++i) cout << ans[i] << '\n';
    return 0;
}

Compilation message

currencies.cpp: In function 'void init(int, int, int)':
currencies.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
currencies.cpp: In function 'void update(int, int, int, int, ll, int)':
currencies.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
currencies.cpp: In function 'll query(int, int, int, int)':
currencies.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:114:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |             int mid = lo[i] + hi[i] >> 1;
      |                       ~~~~~~^~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8644 KB Output is correct
5 Incorrect 8 ms 8796 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Incorrect 10 ms 8916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 11 ms 9052 KB Output is correct
3 Correct 11 ms 9052 KB Output is correct
4 Correct 11 ms 9052 KB Output is correct
5 Correct 779 ms 36564 KB Output is correct
6 Correct 737 ms 40332 KB Output is correct
7 Correct 934 ms 37660 KB Output is correct
8 Correct 1460 ms 47904 KB Output is correct
9 Correct 1376 ms 47800 KB Output is correct
10 Correct 1436 ms 47828 KB Output is correct
11 Correct 981 ms 47896 KB Output is correct
12 Correct 935 ms 47832 KB Output is correct
13 Correct 1002 ms 47820 KB Output is correct
14 Correct 635 ms 47380 KB Output is correct
15 Correct 599 ms 46840 KB Output is correct
16 Correct 759 ms 47556 KB Output is correct
17 Correct 800 ms 47460 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8644 KB Output is correct
5 Incorrect 8 ms 8796 KB Output isn't correct
6 Halted 0 ms 0 KB -