oj.uz

답안 #730487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
730487 2023-04-26T02:58:07 Z kym Two Currencies (JOI23_currencies) C++14
100 / 100
 1180 ms 250720 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> void chmax(T& a, const T b) { a=max(a,b); }
template <typename T> void chmin(T& a, const T b) { a=min(a,b); }
const int MAXN = 1000005;
int n,m,q;
vector<int>V[MAXN];
vector<pi> adj[MAXN];
int P[MAXN];
int head[MAXN];
int heavy[MAXN];
int pos[MAXN];
int parent[MAXN];
int depth[MAXN];
int sz[MAXN];
int cnt=1;
vector<int> W[MAXN];
int dfs(int x, int p){ 
	sz[x]=1;
	parent[x]=p;
	int mx=0;
	for(auto v:adj[x])if(v.f!=p){
		depth[v.f]=depth[x]+1;
		int res=dfs(v.f,x);
		W[v.f]=V[v.s];
		if(res>mx){
			mx=res;
			heavy[x]=v.f;
		}
		sz[x]+=res;
	}
	return sz[x];
}

void decompose(int x, int h) {
	pos[x]=cnt++;
	head[x]=h;
	if(heavy[x]!=-1)decompose(heavy[x],h);
	for(auto v:adj[x]){
		if(v.f==parent[x]||v.f==heavy[x])continue;
		decompose(v.f,v.f);
	}
}

struct node {
	node *l=nullptr,*r=nullptr;
	int sum;
	int num;
	int s,e,m;
	node(int _s, int _e, int val,int numval) {
		s=_s;e=_e;
		m=(s+e)/2;
		sum=val;
		num=numval;
		return;
	}
	node(int _s, int _e, node *L, node *R) {
		s=_s;e=_e;m=(s+e)/2;
		l=L;
		r=R;
		sum=0;
		num=0;
		if(l)sum+=l->sum;
		if(r)sum+=r->sum;
		if(l)num+=l->num;
		if(r)num+=r->num;
	}
} *roots[MAXN];

node* build(int tl, int tr){
	if(tl==tr){
		return new node(tl,tr,(int)0,(int)0);
	}
	int tm=(tl+tr)/2;
	return new node(tl,tr,build(tl,tm), build(tm+1,tr));
}

node* update(node *v, int tl, int tr, int pos, int nval) {
	if(tl==tr){
		return new node(tl,tr,v->sum+nval,v->num+1);
	}
	int tm=(tl+tr)/2;
	if(pos<=tm){
		return new node(tl,tr,update(v->l,tl,tm,pos,nval),v->r);
	} else{
		return new node(tl,tr,v->l,update(v->r,tm+1,tr,pos,nval));
	}
}

pi E[MAXN];
map<int,int> D;
map<int,int> R;
void discretize(vector<int> vec){
	vector<int> dis=vec;
	sort(all(dis));
	dis.resize(unique(all(dis))-dis.begin());
	FOR(i,0,vec.size()-1){
		D[vec[i]]=lower_bound(all(dis),vec[i])-dis.begin()+1;
		R[lower_bound(all(dis),vec[i])-dis.begin()+1]=vec[i];
	}
}
vector<pair<node*,node*>> nodes;
void ask(int x, int y) {
	for(;head[x]!=head[y];y=parent[head[y]]){
		if(depth[head[x]]>depth[head[y]])swap(x,y);
		nodes.pb({roots[pos[head[y]]-1],roots[pos[y]]});
	}
	if(x==y)return;
	if(depth[x]>depth[y])swap(x,y);
	nodes.pb({roots[pos[x]],roots[pos[y]]});
}
int32_t main() 
{
	IAMSPEED
	memset(heavy,-1,sizeof heavy);
	cin >> n >> m >> q;
	FOR(i,1,n-1){
		cin >> E[i].f >> E[i].s;
	}
	vector<int> disc;
	FOR(i,1,m){
		int x; cin >> x;
		int cost; cin>>cost;
		disc.pb(cost);
		V[x].pb(cost);
	}
	discretize(disc);
	FOR(i,1,n-1){
		adj[E[i].f].pb({E[i].s,i}); // this is the edge index
		adj[E[i].s].pb({E[i].f,i}); // this is the edge index
	}
	dfs(1,-1);
	decompose(1,1);
	vector<pi> vec;
	FOR(i,2,n){
		vec.pb({pos[i],i});
	}
	sort(all(vec));
	roots[1]=build(0,m+5);
	for(auto x:vec) {
		roots[x.f]=roots[x.f-1];
		//db(x.s);
		//dbv(W[x.s]);
		for(auto cost:W[x.s]){
			roots[x.f]=update(roots[x.f],0,m+5,D[cost],cost);
		}
		
	}
	while(q--){
		nodes.clear();
		int s,t,x,y; cin >> s >> t >> x >> y;
		ask(s,t);
		for(auto &x:nodes){
			node* lf=x.f;
			node* rg=x.s;
		}
		vector<pair<node*,node*>> V=nodes;
		bool done=0;
		int res=0;
		int val=0;
		int num=0;
		int S,E;
		while(!done){
			
			int lfsum=0;
			int lfnum=0;

			for(auto &x:nodes){
				node* lf=x.f;
				node* rg=x.s;

				S=lf->s;
				E=lf->e;

				if(lf->s==lf->e){
					done=1;
					res=lf->s;
					break;
				}
				lfsum+=rg->l->sum - lf->l->sum;
				lfnum+=rg->l->num - lf->l->num;
			}
			if(val+lfsum<=y){
				val+=lfsum;
				num+=lfnum;

				for(auto &x:nodes){
					x.f=x.f->r;
					x.s=x.s->r;
				}
			} else {
				for(auto &x:nodes){
					x.f=x.f->l;
					x.s=x.s->l;
				}
			}
		}
		//
		// it ended at res. hence, we might be able to get some of res+1 also. 
		--res;
		int extra=0;
		if(R[res+1])extra=(y-val)/R[res+1];
		int ss=num+extra;
		int tot = 0;
		for(auto &x:V){
			node* lf=x.f;
			node* rg=x.s;
			tot+=rg->num-lf->num;
		}
		int spend=tot-ss;
		assert(spend>=0);
		if(spend>x){
			cout<<-1<<'\n';
		} else{
			cout<<x-spend<<'\n';
		}
	}
}

Compilation message

currencies.cpp: In function 'int32_t main()':
currencies.cpp:192:10: warning: unused variable 'lf' [-Wunused-variable]
  192 |    node* lf=x.f;
      |          ^~
currencies.cpp:193:10: warning: unused variable 'rg' [-Wunused-variable]
  193 |    node* rg=x.s;
      |          ^~
currencies.cpp:200:7: warning: variable 'S' set but not used [-Wunused-but-set-variable]
  200 |   int S,E;
      |       ^
currencies.cpp:200:9: warning: variable 'E' set but not used [-Wunused-but-set-variable]
  200 |   int S,E;
      |         ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 78572 KB Output is correct
2 Correct 39 ms 78648 KB Output is correct
3 Correct 37 ms 78540 KB Output is correct
4 Correct 37 ms 78524 KB Output is correct
5 Correct 44 ms 80748 KB Output is correct
6 Correct 46 ms 80808 KB Output is correct
7 Correct 42 ms 80284 KB Output is correct
8 Correct 47 ms 81024 KB Output is correct
9 Correct 45 ms 80972 KB Output is correct
10 Correct 45 ms 80988 KB Output is correct
11 Correct 44 ms 81012 KB Output is correct
12 Correct 44 ms 81096 KB Output is correct
13 Correct 45 ms 81284 KB Output is correct
14 Correct 45 ms 81160 KB Output is correct
15 Correct 44 ms 81064 KB Output is correct
16 Correct 45 ms 81148 KB Output is correct
17 Correct 47 ms 81116 KB Output is correct
18 Correct 47 ms 81096 KB Output is correct
19 Correct 45 ms 81036 KB Output is correct
20 Correct 42 ms 81076 KB Output is correct
21 Correct 44 ms 80980 KB Output is correct
22 Correct 45 ms 81068 KB Output is correct
23 Correct 48 ms 81080 KB Output is correct
24 Correct 53 ms 80992 KB Output is correct
25 Correct 44 ms 81064 KB Output is correct
26 Correct 46 ms 81084 KB Output is correct
27 Correct 48 ms 81016 KB Output is correct
28 Correct 49 ms 81060 KB Output is correct
29 Correct 47 ms 81100 KB Output is correct
30 Correct 45 ms 80732 KB Output is correct
31 Correct 47 ms 80840 KB Output is correct
32 Correct 46 ms 80740 KB Output is correct
33 Correct 49 ms 81288 KB Output is correct
34 Correct 49 ms 81312 KB Output is correct
35 Correct 44 ms 81252 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 78656 KB Output is correct
2 Correct 43 ms 80756 KB Output is correct
3 Correct 42 ms 80716 KB Output is correct
4 Correct 41 ms 80732 KB Output is correct
5 Correct 397 ms 208764 KB Output is correct
6 Correct 405 ms 194516 KB Output is correct
7 Correct 403 ms 175456 KB Output is correct
8 Correct 355 ms 167964 KB Output is correct
9 Correct 365 ms 178796 KB Output is correct
10 Correct 497 ms 221948 KB Output is correct
11 Correct 530 ms 222148 KB Output is correct
12 Correct 535 ms 221980 KB Output is correct
13 Correct 475 ms 222020 KB Output is correct
14 Correct 521 ms 222000 KB Output is correct
15 Correct 396 ms 233464 KB Output is correct
16 Correct 383 ms 234204 KB Output is correct
17 Correct 418 ms 233036 KB Output is correct
18 Correct 405 ms 222276 KB Output is correct
19 Correct 419 ms 222072 KB Output is correct
20 Correct 436 ms 222224 KB Output is correct
21 Correct 353 ms 221468 KB Output is correct
22 Correct 326 ms 221552 KB Output is correct
23 Correct 345 ms 221552 KB Output is correct
24 Correct 356 ms 221640 KB Output is correct
25 Correct 438 ms 221212 KB Output is correct
26 Correct 468 ms 221312 KB Output is correct
27 Correct 456 ms 221368 KB Output is correct
28 Correct 336 ms 222048 KB Output is correct
29 Correct 332 ms 221980 KB Output is correct
30 Correct 382 ms 222036 KB Output is correct
31 Correct 358 ms 221960 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 78548 KB Output is correct
2 Correct 44 ms 81152 KB Output is correct
3 Correct 45 ms 81184 KB Output is correct
4 Correct 53 ms 81148 KB Output is correct
5 Correct 485 ms 191748 KB Output is correct
6 Correct 444 ms 171816 KB Output is correct
7 Correct 691 ms 224704 KB Output is correct
8 Correct 904 ms 250552 KB Output is correct
9 Correct 930 ms 250644 KB Output is correct
10 Correct 983 ms 250608 KB Output is correct
11 Correct 920 ms 249808 KB Output is correct
12 Correct 925 ms 249748 KB Output is correct
13 Correct 1029 ms 249712 KB Output is correct
14 Correct 809 ms 250440 KB Output is correct
15 Correct 894 ms 250364 KB Output is correct
16 Correct 767 ms 250720 KB Output is correct
17 Correct 924 ms 250576 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 78572 KB Output is correct
2 Correct 39 ms 78648 KB Output is correct
3 Correct 37 ms 78540 KB Output is correct
4 Correct 37 ms 78524 KB Output is correct
5 Correct 44 ms 80748 KB Output is correct
6 Correct 46 ms 80808 KB Output is correct
7 Correct 42 ms 80284 KB Output is correct
8 Correct 47 ms 81024 KB Output is correct
9 Correct 45 ms 80972 KB Output is correct
10 Correct 45 ms 80988 KB Output is correct
11 Correct 44 ms 81012 KB Output is correct
12 Correct 44 ms 81096 KB Output is correct
13 Correct 45 ms 81284 KB Output is correct
14 Correct 45 ms 81160 KB Output is correct
15 Correct 44 ms 81064 KB Output is correct
16 Correct 45 ms 81148 KB Output is correct
17 Correct 47 ms 81116 KB Output is correct
18 Correct 47 ms 81096 KB Output is correct
19 Correct 45 ms 81036 KB Output is correct
20 Correct 42 ms 81076 KB Output is correct
21 Correct 44 ms 80980 KB Output is correct
22 Correct 45 ms 81068 KB Output is correct
23 Correct 48 ms 81080 KB Output is correct
24 Correct 53 ms 80992 KB Output is correct
25 Correct 44 ms 81064 KB Output is correct
26 Correct 46 ms 81084 KB Output is correct
27 Correct 48 ms 81016 KB Output is correct
28 Correct 49 ms 81060 KB Output is correct
29 Correct 47 ms 81100 KB Output is correct
30 Correct 45 ms 80732 KB Output is correct
31 Correct 47 ms 80840 KB Output is correct
32 Correct 46 ms 80740 KB Output is correct
33 Correct 49 ms 81288 KB Output is correct
34 Correct 49 ms 81312 KB Output is correct
35 Correct 44 ms 81252 KB Output is correct
36 Correct 41 ms 78656 KB Output is correct
37 Correct 43 ms 80756 KB Output is correct
38 Correct 42 ms 80716 KB Output is correct
39 Correct 41 ms 80732 KB Output is correct
40 Correct 397 ms 208764 KB Output is correct
41 Correct 405 ms 194516 KB Output is correct
42 Correct 403 ms 175456 KB Output is correct
43 Correct 355 ms 167964 KB Output is correct
44 Correct 365 ms 178796 KB Output is correct
45 Correct 497 ms 221948 KB Output is correct
46 Correct 530 ms 222148 KB Output is correct
47 Correct 535 ms 221980 KB Output is correct
48 Correct 475 ms 222020 KB Output is correct
49 Correct 521 ms 222000 KB Output is correct
50 Correct 396 ms 233464 KB Output is correct
51 Correct 383 ms 234204 KB Output is correct
52 Correct 418 ms 233036 KB Output is correct
53 Correct 405 ms 222276 KB Output is correct
54 Correct 419 ms 222072 KB Output is correct
55 Correct 436 ms 222224 KB Output is correct
56 Correct 353 ms 221468 KB Output is correct
57 Correct 326 ms 221552 KB Output is correct
58 Correct 345 ms 221552 KB Output is correct
59 Correct 356 ms 221640 KB Output is correct
60 Correct 438 ms 221212 KB Output is correct
61 Correct 468 ms 221312 KB Output is correct
62 Correct 456 ms 221368 KB Output is correct
63 Correct 336 ms 222048 KB Output is correct
64 Correct 332 ms 221980 KB Output is correct
65 Correct 382 ms 222036 KB Output is correct
66 Correct 358 ms 221960 KB Output is correct
67 Correct 39 ms 78548 KB Output is correct
68 Correct 44 ms 81152 KB Output is correct
69 Correct 45 ms 81184 KB Output is correct
70 Correct 53 ms 81148 KB Output is correct
71 Correct 485 ms 191748 KB Output is correct
72 Correct 444 ms 171816 KB Output is correct
73 Correct 691 ms 224704 KB Output is correct
74 Correct 904 ms 250552 KB Output is correct
75 Correct 930 ms 250644 KB Output is correct
76 Correct 983 ms 250608 KB Output is correct
77 Correct 920 ms 249808 KB Output is correct
78 Correct 925 ms 249748 KB Output is correct
79 Correct 1029 ms 249712 KB Output is correct
80 Correct 809 ms 250440 KB Output is correct
81 Correct 894 ms 250364 KB Output is correct
82 Correct 767 ms 250720 KB Output is correct
83 Correct 924 ms 250576 KB Output is correct
84 Correct 995 ms 224636 KB Output is correct
85 Correct 865 ms 207536 KB Output is correct
86 Correct 681 ms 169060 KB Output is correct
87 Correct 1180 ms 237740 KB Output is correct
88 Correct 1166 ms 237152 KB Output is correct
89 Correct 1082 ms 237792 KB Output is correct
90 Correct 1049 ms 237756 KB Output is correct
91 Correct 1065 ms 237756 KB Output is correct
92 Correct 960 ms 246188 KB Output is correct
93 Correct 883 ms 249032 KB Output is correct
94 Correct 1057 ms 238368 KB Output is correct
95 Correct 1028 ms 238224 KB Output is correct
96 Correct 1089 ms 238272 KB Output is correct
97 Correct 1060 ms 238252 KB Output is correct
98 Correct 799 ms 236900 KB Output is correct
99 Correct 850 ms 236700 KB Output is correct
100 Correct 824 ms 236480 KB Output is correct
101 Correct 770 ms 236816 KB Output is correct
102 Correct 1010 ms 237328 KB Output is correct
103 Correct 989 ms 237228 KB Output is correct
104 Correct 981 ms 237276 KB Output is correct
105 Correct 664 ms 237936 KB Output is correct
106 Correct 682 ms 237404 KB Output is correct
107 Correct 672 ms 237688 KB Output is correct
108 Correct 739 ms 237620 KB Output is correct