Submission #1263961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263961		Bui_Quoc_Cuong	Two Currencies (JOI23_currencies)	C++20	100 / 100	1326 ms	45296 KiB

currencies

/* 29 . 03 . 2008 */ 
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef vector<int> vi ;
typedef vector<pair<int,int>> vii ;
typedef pair<int,int> pii ;
typedef pair<ll,int> pli ;
typedef pair<int,ll> pil ;
typedef pair<ll,ll> pll ;
#define FOR(i,a,b) for(int i(a) ; i <= (int)b ; i++)
#define FORD(i,a,b) for(int i(a) ; i >= (int)b ; i--)
#define FORN(i,a,b) for(int i(a) ; i < (int)b ; i++)
#define all(a) a.begin() , a.end()
#define pb push_back
#define fi first
#define se second
#define endl '\n' 
#define BIT(mask,i) ((mask>>i)&1)
#define builtin_popcount builtin_popcountll
#define MASK(a) (1ll << a) 

template <class T> bool maxi(T &x,T y) { if (x < y) { x = y ; return true ;} return false ;}
template <class T> bool mini(T &x,T y) { if (x > y) { x = y ; return true ;} return false ;}

const int N = 1e5 + 5 ; 

int n, m, q ;

struct Edges {
	int u, v ; 
	ll w ; 
} e[N] ;

struct Queries {
	int st, ed ;
	ll w1, w2 ; 
} Q[N] ;

struct Station {
	int id; ll val ; 
} sta[N] ; 

vector <pil> g[N] ;

void init() {
	cin >> n >> m >> q ; 
	FOR(i, 1, n - 1) {
		int u, v ; cin >> u >> v ; 
		e[i] = {u, v, 0} ;
	}
	FOR(i, 1, m) {
		int p, c ; cin >> p >> c ; 
		sta[i] = {p , c} ; 
		e[p].w+= c ; 
	}
	FOR(i, 1, n - 1) {
		g[e[i].u].pb({e[i].v, e[i].w}) ; g[e[i].v].pb({e[i].u, e[i].w}) ; 
	}
	FOR(i, 1, q) {
		int st, ed ; ll w1, w2 ; cin >> st >> ed >> w1 >> w2 ; 
		Q[i] = {st, ed, w1, w2} ; 
	}
}

struct HeavyLightDecomposition {
	int par[N], head[N], sz[N], cur[N], pos[N], arr[N], h[N] ;
	ll val[N] ;

	void dfs_sz(int u) {
		sz[u] = 1 ; 
		for(pil x : g[u]) {
			int v = x.fi; ll w = x.se ; 
			if(v == par[u]) continue ; 
			par[v] = u ;
			h[v] = h[u] + 1 ; 
			val[v] = w ; 
			dfs_sz(v); 
			sz[u]+= sz[v] ; 
		}
	}

	int crt, timeDFS ;

	void dfs_hld(int u) {
		if(!head[crt]) head[crt] = u ; 
		pos[u] = ++ timeDFS ;
		arr[pos[u]] = u ;
		cur[u] = crt ; 

		int nxt = - 1 ; 
		for(pil x : g[u]) {
			int v = x.fi ; 
			if(v == par[u]) continue ; 
			if(nxt == -1 || sz[v] > sz[nxt]) nxt = v ; 
		}

		if(nxt != - 1) dfs_hld(nxt) ; 

		for(pil x : g[u]) {
			int v = x.fi ; 
			if(v == par[u] || v==nxt) continue ; 
			crt++ ; 
			dfs_hld(v) ; 
		}
	}

	ll bit[N][3] ;	

	void up(int u, ll val, int t) {
		for(int i = u; i <= n ; i+=i&-i) bit[i][t]+= val ; 
	}

	ll get(int u, int t) {
		ll sum = 0 ;
		for(int i = u ; i ; i-=i&-i) sum+= bit[i][t] ; 
		return sum ; 
	}

	ll get(int l, int r, int t) {
		return get(r, t) - get(l - 1, t) ; 
	}

	int lca(int u, int v) {
		while(cur[u] != cur[v]) {
			if(cur[u] > cur[v]) u = par[head[cur[u]]] ; 
			else v = par[head[cur[v]]] ; 
		}
		if(h[u] < h[v]) return u ; 
		else return v ; 
	}

	ll SUMPATH(int u, int v, int t) {
		int p = lca(u, v) ; 
		ll res = 0 ;
		while(cur[u]!=cur[p]) {
			res+= get(pos[head[cur[u]]], pos[u], t) ; 
			u = par[head[cur[u]]] ; 
		}
		while(cur[v]!=cur[p]) {
			res+= get(pos[head[cur[v]]], pos[v], t) ; 
			v = par[head[cur[v]]] ; 
		}
		if(pos[u] < pos[v]) res+= get(pos[u] + 1, pos[v], t) ; 
		else if(pos[v] < pos[u]) res+= get(pos[v] + 1, pos[u], t) ; 
		return res ; 
	}

	void init() {
		dfs_sz(1) ; dfs_hld(1) ; 
	}

	void reset() {
		memset(bit, 0, sizeof bit) ; 
	}
} hld ;

ll L[N], R[N], ans[N] ;
vi Quer[N] ; 

void solve() {
	hld.init() ;

	sort(sta + 1, sta + 1 + m, [](Station u, Station v) {
		return u.val < v.val ;
	}) ; 

	memset(ans, 0x3f, sizeof ans) ; 

	FOR(i, 1, q) L[i] = 0, R[i] = m ; 

	
	FOR(i, 1, m) {
		int u = e[sta[i].id].u, v = e[sta[i].id].v ;
		if(v == hld.par[u]) swap(e[sta[i].id].u, e[sta[i].id].v) ;
		// cout << u << ' ' << v << endl ; 
	}	


	while(1) {
		hld.reset() ; 
		FOR(i, 1, m) Quer[i].clear() ; 

		bool ok = false ; 
		FOR(i, 1, q) if(L[i] <= R[i]) {
			ok = true ; 
			Quer[(L[i] + R[i])/2].pb(i) ; 
		}

		if(!ok) break ; 
		FOR(i, 1, m) {
			int v = e[sta[i].id].v ; 
			hld.up(hld.pos[v], 1, 1) ; 
		}

		FOR(i, 0, m) {
			if(i > 0) {
				ll w = sta[i].val ;
				int v = e[sta[i].id].v ; 
				hld.up(hld.pos[v], -1, 1) ; 
				hld.up(hld.pos[v], w, 2) ; 
			}

			for(int id : Quer[i]) {
				int u = Q[id].st, v = Q[id].ed ; ll silver = Q[id].w2 ; 

				if(hld.SUMPATH(u, v, 2) <= silver) {
					ans[id] = hld.SUMPATH(u, v, 1) ; 
					L[id] = i + 1 ; 
				} else {
					R[id] = i - 1 ; 
				}
			} 
		}
	}	

	FOR(i, 1, q) cout << max(Q[i].w1- ans[i], 1ll * -1) << endl ;
}	
signed main() {
    #define task ""
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; 
    if(fopen(".inp","r")) {
        freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ; 
    }
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ; 
    }
    init() ;
    solve() ;
    cerr << "\nTime : " << clock() * 0.001 << "s" << endl ;
    return 0 ; 
}
/* Watbor */

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:223:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  223 |         freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
currencies.cpp:223:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  223 |         freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ;
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~
currencies.cpp:226:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |         freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:226:48: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |         freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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