Submission #1268008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268008		phuocrucpp	Two Currencies (JOI23_currencies)	C++20	100 / 100	3051 ms	54180 KiB

currencies

/*ㅤ∧＿∧
　(　･∀･)
　(　つ┳⊃
ε (_)へ⌒ヽﾌ
 (　　(　･ω･)
 ◎―◎   ⊃  ⊃
BePhuongSuperSuwi
From TK4 - CHT
ㅤㅤ／ ⌒＼____
　 /・　　 ）　　\
　/ノへ ノ　　　 /|
ノ　　  ＼\ |/_/_/*/


#include<bits/stdc++.h>
#define task "main"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define int long long
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii, ii>
#define base 341
#define MASK(i) (1ll << i)
#define oo 1e18
#define isOn(x,i) ((x) & MASK(i))
#define bitOn(x,i) ((x) | MASK(i))
#define bitOff(x,i) ((x) & ~MASK(i))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
using namespace std;
//using namespace __gnu_pbds;
const int maxn = 1e5 + 5;

int n, m, test, l[maxn], r[maxn];
vector <int> query[maxn];

struct pt{
    int pos, val;
} q[maxn];

bool ss(pt a, pt b) {
    return a.val < b.val;
}

vector<ii> v[maxn];
int sz[maxn], Head[maxn], h[maxn], par[maxn], Pos[maxn], Id[maxn], chain, timer, tin[maxn], tout[maxn], ed[maxn];

void dfs(int u, int p) {
	sz[u] = 1;
	for (auto e : v[u]) {
        int x = e.fi, y = e.se;
		if (x == p) continue;
		h[x] = h[u] + 1;
		par[x] = u;
        ed[y] = x;

		dfs(x, u);
		sz[u] += sz[x];
	}
}

void hld(int u, int p) {
	if (!Head[chain]) {
		Head[chain] = u;
	}
	Id[u] = chain;
	Pos[u] = tin[u] = ++timer;
	int nxt = 0;
	for (auto e: v[u]) {
        int x = e.fi;
		if (x == p) continue;
		if (nxt == 0 || sz[nxt] < sz[x]) nxt = x;
	}
	if (nxt) hld(nxt, u);
	for (auto e : v[u]) {
        int x = e.fi;
		if (x == p || x == nxt) continue;
		chain++;
		hld(x, u);
	}
	tout[u] = timer;
}

struct HLD{
    int st[4 * maxn];
    void update(int id, int l, int r, int pos, int val) {
        if (l == r) {
            st[id] += val;
            return;
        }
        int m = (l + r) / 2;
        if (pos <= m) update(id * 2, l, m, pos, val);
        else update(id * 2 + 1, m + 1, r, pos, val);
        st[id] = st[id * 2] + st[id * 2 + 1];
    }

    int get(int id, int l, int r, int u, int v) {
        if (u > r || v < l) return 0;
        if (l >= u && r <= v) return st[id];
        int m = (l + r)/2;
        return get(id * 2, l, m, u, v) + get(id * 2 + 1, m + 1, r, u, v);
    }

    void init() {
        for (int i = 0; i <= 4 * n; i++) st[i] = 0;
    }

    int Query(int u, int v) {
        int ans = 0;
        while (Id[u] != Id[v]) {
            if (h[Head[Id[u]]] > h[Head[Id[v]]]) swap(u,v);
            ans += get(1,1,n,Pos[Head[Id[v]]], Pos[v]);
            v = par[Head[Id[v]]];
        }
        if (h[u] > h[v]) swap(u,v);
        ans += get(1,1,n,Pos[u] + 1, Pos[v]);
        return ans;
    }
} hld1, hld2;


int s[maxn], t[maxn], x[maxn], y[maxn], res[maxn];

main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin >> n >> m >> test;
    for (int i = 1; i < n; i++) {
        int l, r;
        cin >> l >> r;
        v[l].pb({r, i}); v[r].pb({l, i});
    }

    for (int i = 1; i <= m; i++) {
        cin >> q[i].pos >> q[i].val;
    }

    sort(q + 1, q + m + 1, ss);

    for (int i = 1; i <= test; i++) {
        cin >> s[i] >> t[i] >> x[i] >> y[i];
        l[i] = 0, r[i] = m, res[i] = -1;
    }

    dfs(1, -1);
   	chain = 1;
   	hld(1, -1);

    while(true) {
    	bool ok = false;
    	for (int i = 1; i <= test; i++) {
    		if (l[i] > r[i]) continue;
    		ok = true;
    		int mid = (l[i] + r[i])/2;
    		query[mid].pb(i);
    	}
    	if (!ok) break;
    	//reset_ctdl;
    	hld1.init();
    	hld2.init();

    	for (int mid = 0; mid <= m; mid++) {
    		if (mid > 0) {
                int id = q[mid].pos, val = q[mid].val;
                hld2.update(1, 1, n, tin[ed[id]], 1);
                hld1.update(1, 1, n, tin[ed[id]], val);
    		}
    		for (auto id : query[mid]) {
    			if (hld1.Query(s[id], t[id]) <= y[id]) {
    				res[id] = hld2.Query(s[id], t[id]);
    				l[id] = mid + 1;
    			}
    			else r[id] = mid - 1;
    		}
    		query[mid].clear();
    	}
    }

    hld2.init();
    for (int i = 1; i <= m; i++) {
        int id = q[i].pos;
        hld2.update(1, 1, n, tin[ed[id]], 1);
    }

    for (int i = 1; i <= test; i++) {
 //       cout << res[i] << " ";
        int val = x[i] - (hld2.Query(s[i], t[i]) - res[i]);
   //     cout << x[i] << " " << hld2.Query(s[i], t[i]) << " ";
        if (val < 0) cout << "-1" << endl;
        else cout << val << endl;
    }

}

Compilation message (stderr)

currencies.cpp:129:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  129 | main() {
      | ^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32