oj.uz

답안 #730484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
730484 2023-04-26T02:50:56 Z kym Two Currencies (JOI23_currencies) C++14
28 / 100
 529 ms 427492 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);
		db2(pos[head[y]]-1,pos[y]);
		nodes.pb({roots[pos[head[y]]-1],roots[pos[y]]});
	}
	if(x==y)return;
	if(depth[x]>depth[y])swap(x,y);
	db2(pos[x],pos[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,n);
	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,n,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;
				assert(lf->s==rg->s && lf->e==rg->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 died at res+1. hence, we might be able to get some of res+1 also. 
		db2(res,R[res]);
		db2(val,num);
		--res;
		int extra=0;
		if(R.find(res+1)!=R.end())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;
		db2(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:194:10: warning: unused variable 'lf' [-Wunused-variable]
  194 |    node* lf=x.f;
      |          ^~
currencies.cpp:195:10: warning: unused variable 'rg' [-Wunused-variable]
  195 |    node* rg=x.s;
      |          ^~
currencies.cpp:202:7: warning: variable 'S' set but not used [-Wunused-but-set-variable]
  202 |   int S,E;
      |       ^
currencies.cpp:202:9: warning: variable 'E' set but not used [-Wunused-but-set-variable]
  202 |   int S,E;
      |         ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 78548 KB Output is correct
2 Correct 37 ms 78636 KB Output is correct
3 Correct 38 ms 78616 KB Output is correct
4 Correct 36 ms 78608 KB Output is correct
5 Runtime error 106 ms 163780 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 78600 KB Output is correct
2 Correct 42 ms 80864 KB Output is correct
3 Correct 45 ms 80812 KB Output is correct
4 Correct 44 ms 80764 KB Output is correct
5 Correct 367 ms 214392 KB Output is correct
6 Correct 419 ms 197408 KB Output is correct
7 Correct 371 ms 182116 KB Output is correct
8 Correct 336 ms 178640 KB Output is correct
9 Correct 330 ms 184764 KB Output is correct
10 Correct 515 ms 227252 KB Output is correct
11 Correct 520 ms 227224 KB Output is correct
12 Correct 502 ms 227196 KB Output is correct
13 Correct 528 ms 227180 KB Output is correct
14 Correct 477 ms 227164 KB Output is correct
15 Correct 412 ms 239208 KB Output is correct
16 Correct 362 ms 240004 KB Output is correct
17 Correct 423 ms 238620 KB Output is correct
18 Correct 425 ms 227656 KB Output is correct
19 Correct 435 ms 227596 KB Output is correct
20 Correct 434 ms 227764 KB Output is correct
21 Correct 352 ms 226020 KB Output is correct
22 Correct 347 ms 226268 KB Output is correct
23 Correct 328 ms 226268 KB Output is correct
24 Correct 369 ms 226248 KB Output is correct
25 Correct 412 ms 226724 KB Output is correct
26 Correct 472 ms 226800 KB Output is correct
27 Correct 455 ms 226644 KB Output is correct
28 Correct 342 ms 227116 KB Output is correct
29 Correct 346 ms 227056 KB Output is correct
30 Correct 441 ms 227164 KB Output is correct
31 Correct 442 ms 227224 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 78548 KB Output is correct
2 Correct 44 ms 81268 KB Output is correct
3 Correct 47 ms 81232 KB Output is correct
4 Correct 49 ms 81296 KB Output is correct
5 Correct 522 ms 202456 KB Output is correct
6 Correct 450 ms 183916 KB Output is correct
7 Runtime error 529 ms 427492 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 78548 KB Output is correct
2 Correct 37 ms 78636 KB Output is correct
3 Correct 38 ms 78616 KB Output is correct
4 Correct 36 ms 78608 KB Output is correct
5 Runtime error 106 ms 163780 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -