Submission #841844

#	Time	Username	Problem	Language	Result	Execution time	Memory
841844		eltu0815	Two Currencies (JOI23_currencies)	C++14	100 / 100	2123 ms	47680 KiB

currencies

#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 j = 1; j < 20; ++j) for(int i = 1; i <= n; ++i) 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 (stderr)

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: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32