oj.uz

Submission #851576

# Submission time Handle Problem Language Result Execution time Memory
851576 2023-09-20T07:28:45 Z willychan Two Currencies (JOI23_currencies) C++14
0 / 100
 3 ms 6236 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

const int N = 1e5+5;
vector<pair<int,int> > side[N];
vector<pair<int,int> > edgeset;

pair<int,int> father[N][20];
int dep[N];
void dfs(int c){
	for(auto i : side[c]){
		if(father[i.first][0].first==0) {
			dep[i.first] = dep[c]+1;
			father[i.first][0] = {c,i.second};
			dfs(i.first);
		}
	}
}

int get(int a,int b){
	if(a==b) return 0;
	ll sum =0;
	if(dep[a]>dep[b]) swap(a,b);
	if(dep[b]>dep[a]){
		for(int j=19;j>=0;j--){
			if(dep[father[b][j].first]>dep[a]){
				sum+=father[b][j].second;
				b = father[b][j].first;
			}
			
		}
		sum+=father[b][0].second;
		b = father[b][0].first;
	}
	assert(dep[a]==dep[b]);
	if(a==b) return sum;
	for(int j=19;j>=0;j--){
		if(father[a][j].first!=father[b][j].first){
			sum+=father[a][j].second;
			sum+=father[b][j].second;
			a=father[a][j].first;
			b=father[b][j].first;
		}
	}
	sum+=father[a][0].second;
	sum+=father[b][0].second;
	return sum;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m,q;cin>>n>>m>>q;
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		side[a].push_back({b,0});
		side[b].push_back({a,0});
		edgeset.push_back({a,side[a].size()-1});
		edgeset.push_back({b,side[b].size()-1});
	}
	int C;
	for(int i=0;i<m;i++){
		int p;cin>>p>>C;
		p--;
		pair<int,int> ff=edgeset[2*p];
		pair<int,int> ss=edgeset[2*p+1];
		side[ff.first][ff.second].second++;
		side[ss.first][ss.second].second++;
	}
	for(int i=1;i<20;i++) father[1][i] ={1,0};
	dfs(1);
	for(int j=1;j<20;j++){
		for(int i=2;i<=n;i++){
			int v = father[i][j-1].second+father[father[i][j-1].first][j-1].second;
			father[i][j] = {father[father[i][j-1].first][j-1].first,v};
		}
	}
	while(q--){
		int a,b,x,y;cin>>a>>b>>x>>y;
		int cnt = get(a,b);
		int c = y/C;
		int howmany = max(0,cnt-c);
		cout<<max(-1,x-howmany)<<"\n";
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6232 KB Output isn't correct
2 Halted 0 ms 0 KB -