Submission #925768

#	Time	Username	Problem	Language	Result	Execution time	Memory
925768		pcc	Min-max tree (BOI18_minmaxtree)	C++17	0 / 100	1054 ms	43336 KiB

minmaxtree

#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;

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);
			ans += dfs(s,t,INT_MAX);
		}
		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,0,N,0);
	cin>>Q;
	while(Q--){
		char c;
		int a,b,w;
		cin>>c>>a>>b>>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*2+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]);
		if(mp.find(low)==mp.end())mp[low] = mp.size()+1;
		if(mp.find(high)==mp.end())mp[high] = mp.size()+1;
		rmp[mp[low]] = low;
		rmp[mp[high]] = high;
		//cout<<i<<':'<<low<<','<<high<<":"<<rmp[low]<<','<<rmp[high]<<endl;
		low = mp[low],high = mp[high];
		din.add_edge(i,low+N,1);
		din.add_edge(i,high+N,1);
		din.add_edge(0,i,1);
		//cout<<i<<endl;
	}
	//cout<<"GRAPH MADE"<<endl;
	for(auto &i:mp)din.add_edge(i.sc+N,N*2,1);
	din.flow(0,N*2);
	din.getans();
	for(int i = 2;i<=N;i++){
		cout<<par[i]<<' '<<i<<' '<<ans[i]<<'\n';
	}
	return 0;
}

Compilation message (stderr)

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: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42