oj.uz

Submission #925806

# Submission time Handle Problem Language Result Execution time Memory
925806 2024-02-12T09:07:08 Z pcc Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 512 ms 55852 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 7e4+10;
int idx[mxn],par[mxn],link_top[mxn],sz[mxn],dep[mxn],bs[mxn],cnt,ans[mxn];
vector<int> tree[mxn];
int N,Q;
map<int,int> mp,rmp;
set<int> used;

struct SEG{
	int seg[mxn*4];
	SEG(){
		memset(seg,-1,sizeof(seg));
	}
	void push(int now){
		if(seg[now] == -1)return;
		seg[now*2+2] = seg[now*2+1] = seg[now];
		seg[now] = -1;
		return;
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now] = v;
			return;
		}
		int mid = (l+r)>>1;
		push(now);
		if(mid>=s)modify(now*2+1,l,mid,s,e,v);
		if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
	}
	int getval(int now,int l,int r,int p){
		if(l == r||seg[now] != -1)return seg[now];
		int mid = (l+r)>>1;
		if(mid>=p)return getval(now*2+1,l,mid,p);
		else return getval(now*2+2,mid+1,r,p);
	}
};

SEG mx,mn;
vector<pair<int,pii>> mxv,mnv;

struct DINIC{
	struct E{
		int t,c,f;
		E(){
			t = c= f = 0;
		}
		E(int tt,int cc):t(tt),c(cc),f(0){}
	};
	vector<E> e;
	vector<int> ptr,lvl;
	queue<int> q;
	vector<vector<int>> p;
	DINIC(int n = 0){
		ptr = lvl = vector<int>(n,0);
		e.clear();
		p = vector<vector<int>>(n);
	}
	void add_edge(int a,int b,int c,int d = 0){
		p[a].push_back(e.size());
		e.push_back(E(b,c));
		p[b].push_back(e.size());
		e.push_back(E(a,d));
		return;
	}
	bool bfs(int s,int t){
		fill(lvl.begin(),lvl.end(),-1);
		q.push(s);
		lvl[s] = 0;
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			for(auto &eid:p[now]){
				int nxt = e[eid].t;
				if(e[eid].f == e[eid].c||lvl[nxt] != -1)continue;
				lvl[nxt] = lvl[now]+1;
				q.push(nxt);
			}
		}
		return lvl[t] != -1;
	}
	int dfs(int now,int t,int f){
		if(now == t||!f)return f;
		for(int &i = ptr[now];i<p[now].size();i++){
			int eid = p[now][i];
			if(e[eid].c == e[eid].f||lvl[e[eid].t] != lvl[now]+1)continue;
			if(int re = dfs(e[eid].t,t,min(f,e[eid].c-e[eid].f))){
				e[eid].f += re;
				e[eid^1].f -= re;
				return re;
			}
		}
		return 0;
	}
	int flow(int s,int t){
		int ans = 0;
		while(bfs(s,t)){
			fill(ptr.begin(),ptr.end(),0);
			while(int re = dfs(s,t,INT_MAX))ans += re;
		}
		return ans;
	}
	void getans(){
		for(int i = 0;i<e.size();i+=2){
			if(e[i].f == e[i].c&&e[i].t>N&&e[i^1].t<=N){
				ans[e[i^1].t] = rmp[e[i].t-N];
			}
		}
	}
};

void dfs1(int now){
	sz[now] = 1;
	for(auto nxt:tree[now]){
		if(nxt == par[now])continue;
		par[nxt] = now;
		dep[nxt] = dep[now]+1;
		dfs1(nxt);
		sz[now] += sz[nxt];
		if(!bs[now]||sz[bs[now]]<sz[nxt])bs[now] = nxt;
	}
	return;
}
void dfs2(int now,int top){
	link_top[now] = top;
	idx[now] = ++cnt;
	if(bs[now])dfs2(bs[now],top);
	for(auto nxt:tree[now]){
		if(nxt == par[now]||nxt == bs[now])continue;
		dfs2(nxt,nxt);
	}
	return;
}

inline void calc(int a,int b,int w,SEG &segtree){
	int ta = link_top[a],tb = link_top[b];
	while(ta != tb){
		if(dep[ta]<dep[tb]){
			swap(a,b);
			swap(ta,tb);
		}
		segtree.modify(0,1,N,idx[ta],idx[a],w);
		a = par[ta];
		ta = link_top[a];
	}
	if(idx[a]>idx[b])swap(a,b);
	if(a != b)segtree.modify(0,1,N,idx[a]+1,idx[b],w);
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs1(1);
	dfs2(1,1);
	mx.modify(0,1,N,1,N,INT_MAX);
	mn.modify(0,1,N,1,N,0);
	cin>>Q;
	for(int i = 0;i<Q;i++){
		char c;
		int a,b,w;
		cin>>c>>a>>b>>w;
		used.insert(w);
		if(c == 'M')mxv.push_back({w,{a,b}});
		else mnv.push_back({w,{a,b}});
	}
	sort(mxv.rbegin(),mxv.rend());
	sort(mnv.begin(),mnv.end());
	for(auto &i:mxv)calc(i.sc.fs,i.sc.sc,i.fs,mx);
	for(auto &i:mnv)calc(i.sc.fs,i.sc.sc,i.fs,mn);
	DINIC din(N*5+2);
	for(int i = 2;i<=N;i++){
		int low = mn.getval(0,1,N,idx[i]),high = mx.getval(0,1,N,idx[i]);
		assert(low<=high);
		if(mp.find(low)==mp.end())mp[low] = mp.size()+1;
		if(mp.find(high)==mp.end())mp[high] = mp.size()+1;
		ans[i] = low;
		rmp[mp[low]] = low;
		rmp[mp[high]] = high;
		low = mp[low],high = mp[high];
		//cout<<i<<':'<<low<<','<<high<<":"<<rmp[low]<<','<<rmp[high]<<endl;
		if(used.find(rmp[low]) != used.end())din.add_edge(i,low+N,1);
		if(used.find(rmp[high]) != used.end())din.add_edge(i,high+N,1);
		din.add_edge(0,i,1);
		//cout<<i<<endl;
	}
	for(auto &i:used)din.add_edge(mp[i]+N,N*5,1);
	//cout<<"GRAPH MADE"<<endl;
	/*
	for(auto &i:rmp)cout<<i.fs<<':'<<i.sc<<',';cout<<endl;
	for(int i = 0;i<din.e.size();i+=2){
		cout<<din.e[i^1].t<<' '<<din.e[i].t<<endl;
	}
   */
	int tans = din.flow(0,N*5);
	assert(tans == Q);
	din.getans();
	for(int i = 2;i<=N;i++){
		cout<<par[i]<<' '<<i<<' '<<ans[i]<<'\n';
	}
	return 0;
}

Compilation message

minmaxtree.cpp: In member function 'int DINIC::dfs(int, int, int)':
minmaxtree.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int &i = ptr[now];i<p[now].size();i++){
      |                         ~^~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'void DINIC::getans()':
minmaxtree.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<DINIC::E>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   for(int i = 0;i<e.size();i+=2){
      |                 ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 45228 KB Output is correct
2 Correct 249 ms 42232 KB Output is correct
3 Correct 214 ms 42140 KB Output is correct
4 Correct 229 ms 46100 KB Output is correct
5 Correct 232 ms 41892 KB Output is correct
6 Correct 239 ms 42232 KB Output is correct
7 Correct 228 ms 41592 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 33284 KB Output is correct
2 Correct 153 ms 34552 KB Output is correct
3 Correct 130 ms 33952 KB Output is correct
4 Correct 122 ms 35516 KB Output is correct
5 Correct 158 ms 36352 KB Output is correct
6 Correct 167 ms 37472 KB Output is correct
7 Correct 170 ms 35556 KB Output is correct
8 Correct 185 ms 36096 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 242 ms 45228 KB Output is correct
6 Correct 249 ms 42232 KB Output is correct
7 Correct 214 ms 42140 KB Output is correct
8 Correct 229 ms 46100 KB Output is correct
9 Correct 232 ms 41892 KB Output is correct
10 Correct 239 ms 42232 KB Output is correct
11 Correct 228 ms 41592 KB Output is correct
12 Correct 149 ms 33284 KB Output is correct
13 Correct 153 ms 34552 KB Output is correct
14 Correct 130 ms 33952 KB Output is correct
15 Correct 122 ms 35516 KB Output is correct
16 Correct 158 ms 36352 KB Output is correct
17 Correct 167 ms 37472 KB Output is correct
18 Correct 170 ms 35556 KB Output is correct
19 Correct 185 ms 36096 KB Output is correct
20 Correct 468 ms 44208 KB Output is correct
21 Correct 322 ms 41232 KB Output is correct
22 Correct 299 ms 40768 KB Output is correct
23 Correct 321 ms 40760 KB Output is correct
24 Correct 474 ms 54980 KB Output is correct
25 Correct 465 ms 55852 KB Output is correct
26 Correct 400 ms 53544 KB Output is correct
27 Correct 436 ms 54080 KB Output is correct
28 Correct 499 ms 45840 KB Output is correct
29 Correct 451 ms 45528 KB Output is correct
30 Correct 359 ms 42292 KB Output is correct
31 Correct 344 ms 42800 KB Output is correct
32 Correct 512 ms 45012 KB Output is correct
33 Correct 422 ms 43320 KB Output is correct
34 Correct 386 ms 43312 KB Output is correct
35 Correct 396 ms 42568 KB Output is correct