Submission #888802

#	Time	Username	Problem	Language	Result	Execution time	Memory
888802		vjudge1	Two Currencies (JOI23_currencies)	C++17	38 / 100	5044 ms	70284 KiB

currencies

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

bool YES(bool f){ if(f) cout << "Yes\n" ; else cout << "No\n" ; return f ; }
void YES(){cout << "Yes\n" ;}
void NO(){cout << "No\n" ;}
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define ld long double
#define pii pair <int , int>
#define ff first
#define ss second
#define endl '\n'

const int N = 2e5 + 5 ;
const int inf = 1e18 ;
const int mod = 1e9 + 7 ;
const double eps = 1e-8 ;

int binpow( int a , int b ){
  if ( b == 0 ) return 1 ;
  int x = binpow ( a , b/2 ) ;
  if ( !(b%2) ) return (x*x) ;
  return (x*x*a) ;
}
template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}

//code

int n , m , q , tmp = -2 , l , timer ;
int a[N] , b[N] , c[N] , x[N] , y[N] , f[N] , s[N] , cnt[N] , ans[N] , par[N] , pr[N] , tin[N] , tout[N] ;
int up[N][30] ;
vector <int> ind[N] , cost[N] ;
int r[N] ;
vector <pii> g[N] ;
multiset <int> cur ;

bool dfs ( int v , int s , int p ){
	if ( v == s ) return 1 ;
	for ( auto to : g[v] ){
		if ( to.ff != p ){
			cur.insert(to.ss) ;
			if ( !dfs(to.ff,s,v) ) cur.erase(cur.find(to.ss)) ;
			else return 1 ;
		}
	}
	return 0 ;
}

void dfs1 ( int v , int p , int sum ){
	pr[v] = sum ;
	for ( auto to : g[v] ){
		if ( to.ff != p ){
			sum += to.ss ;
			dfs1( to.ff , v , sum ) ;
			sum -= to.ss ;
		}
	}
}

void dfsa( int v , int p ){
	tin[v] = ++timer ;
	up[v][0] = p ;
	for ( int i = 1;  i <= l ; i ++ ) up[v][i] = up[up[v][i-1]][i-1] ;
	for ( auto to : g[v] ){
		if ( to.ff != p ) dfsa(to.ff,v) ;
	}
	tout[v] = ++timer ;
}

bool upper ( int a , int b ){
	return ( tin[a] <= tin[b] && tout[a] >= tout[b] ) ;
}

int lca ( int a  , int b ){
	if ( upper(a,b) ) return a ;
	if ( upper(b,a) ) return b ;
	for ( int i = l ; i >= 0 ; i -- ){
		if ( !upper(up[a][i] , b) ) a = up[a][i] ;
	}
	return up[a][0] ;
}

void solve(){
	
	cin >> n >> m >> q ;
	while ( ( 1 << (l) ) <= n ) l ++ ;
	for ( int i = 1 ; i < n ; i ++ ) {
		cin >> a[i] >> b[i] ;
		c[i] = inf ;
	}
	for ( int i = 0 ; i < m ; i ++ ){
		int x , y ; cin >> x >> y ;
		if ( tmp == -2 ) tmp = y ;
		else if ( tmp != y ) tmp = -1 ;
		cost[x].push_back(y) ; cnt[x] ++ ;
	} 
	for ( int i = 0 ; i < q ; i ++ ) cin >> x[i] >> y[i] >> f[i] >> s[i] ;
	if ( tmp != -1 ){
		for ( int i = 1 ; i < n ; i ++ ){
			g[a[i]].push_back({b[i],cnt[i]}) ;
			g[b[i]].push_back({a[i],cnt[i]}) ;
		}
		for ( int i = 0 ; i < q ; i ++ ) s[i] /= tmp , s[i] += f[i] ;
		dfsa(1,1) ;
		dfs1(1,0,0) ;
		for ( int i = 0 ; i < q ; i ++ ){
			int par = lca ( x[i] , y[i] ) , cur ;
			//cout << x[i] << ' ' << y[i] << ' ' << par << endl ;
			if ( par == x[i] ) cur = pr[y[i]]-pr[x[i]] ;
			else if ( par == y[i] ) cur = pr[x[i]]-pr[y[i]] ;
			else cur = pr[x[i]]+pr[y[i]]-pr[par]*2 ;
			if ( s[i] < cur ) cout << "-1\n" ;
			else cout << min ( f[i] , s[i]-cur ) << endl ;
		}
		return ;
	}
	for ( int i = 1 ; i < n ; i ++ ){
		if ( c[i] == inf ) c[i] = 0 ;
		g[a[i]].push_back({b[i],i}) ;
		g[b[i]].push_back({a[i],i}) ;
	}
	for ( int i = 0 ; i < q ; i ++ ){
		cur.clear() ;
		dfs ( x[i] , y[i] ,0) ;
		multiset <int> st ;
		for ( auto j : cur ) for ( auto k : cost[j] ) st.insert(k) ;
		for ( auto j : st ){
			if ( j <= s[i] ) s[i] -= j ;
			else f[i] -- ;
			if (f[i]<0) break ;
		}
		if ( f[i] < 0 ) cout << "-1\n" ;
		else cout << f[i] << endl ;
	}
	
}

signed main(){
    //ios ;
	int t = 1 ;
	//cin >> t ;
	while ( t -- ) solve() ;
}

Compilation message (stderr)

currencies.cpp: In function 'void fopn(std::string)':
currencies.cpp:10:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:10:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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