Submission #1202542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202542		8pete8	Min-max tree (BOI18_minmaxtree)	C++20	0 / 100	134 ms	74012 KiB

minmaxtree

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native,sse,sse2,sse3")
using namespace std;
#define int long long
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=31,Mxn=6e6,base=131;
//#undef int
int n,k,m,q,L;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
vector<int>adj[mxn+10];
int up[mxn+10][lg+1],h[mxn+10],pa[mxn+10];
void dfs(int cur,int p){
	for(auto i:adj[cur])if(i!=p){
		h[i]=h[cur]+1;
		pa[i]=cur;
		dfs(i,cur);
		up[i][0]=cur;
	}
}
int lca(int a,int b){
	if(h[a]<h[b])swap(a,b);
	int k=h[a]-h[b];
	for(int i=0;i<=lg;i++)if(k&(1LL<<i))a=up[a][i];
	if(a==b)return a;
	for(int i=lg;i>=0;i--)if(up[a][i]!=up[b][i]){
		a=up[a][i];
		b=up[b][i];
	}
	return up[a][0];
}
priority_queue<pii>T[2][mxn+10];
int H[mxn+10],val[mxn+10];
int P[mxn+10][2];
void getpa(int cur,int p){
	for(auto i:adj[cur])if(i!=p){
		getpa(i,cur);
		for(int j=0;j<2;j++)if(T[j][i].size()>T[j][cur].size()){
			swap(T[j][i],T[j][cur]);
			while(!T[j][i].empty())T[j][cur].push(T[j][i].top()),T[j][i].pop();
		}
	}
	for(int j=0;j<2;j++){
		while(!T[j][cur].empty()&&H[T[j][cur].top().s]>=h[cur])T[j][cur].pop();
		if(T[j][cur].size())P[cur][j]=T[j][cur].top().s;
		
	}
}
struct edge{
	int flow,cap,to;
};
struct dinic{
	vector<edge>E;
	vector<int>go[mxn+10];
	int lvl[mxn+10],at[mxn+10];
	void addedge(int a,int b,int c){
		//a->b;
		go[a].pb(E.size());
		E.pb({0,c,b});
		go[b].pb(E.size());
		E.pb({0,0,a});
	}
	bool bfs(int S,int T){
		queue<int>Q;
		Q.push(S);
		for(int i=0;i<=n+q+1;i++)lvl[i]=-1,at[i]=0;
		lvl[S]=0;
		while(!Q.empty()){
			int cur=Q.front();
			Q.pop();
			for(auto i:go[cur]){
				int v=E[i].to;
				if(lvl[v]==-1&&E[i].cap-E[i].flow>0){
					lvl[v]=lvl[cur]+1;
					Q.push(v);
				}
			}
		}
		return lvl[T]>=0;
	}
	int dfs(int cur,int T,int F){
		if(cur==T)return F;
		for(;at[cur]<go[cur].size();at[cur]++){
			edge &v=E[go[cur][at[cur]]];
			if(lvl[v.to]<lvl[cur])continue;
			if(v.cap-v.flow>0){
				int x=dfs(v.to,T,min(F,v.cap-v.flow));
				if(x==0)continue;
				v.flow+=x;
				E[go[cur][at[cur]]^1].flow-=x;
				return x;
			}
		}
		return 0;
	}
	int maxflow(int S,int T){
		int ans=0;
		while(bfs(S,T)){
			while(int x=dfs(S,T,inf))ans+=x;
		}
		return ans;
	}
}t;
int32_t main(){
	fastio
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for(int i=0;i<=lg;i++)up[1][i]=1;
	dfs(1,-1);
	for(int j=1;j<=lg;j++)for(int i=1;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
	cin>>q;
	for(int i=1;i<=q;i++){
		char x;cin>>x;
		int a,b,c;cin>>a>>b>>c;
		val[i]=c;
		int node=lca(a,b);
		H[i]=h[node];
		int k=(x=='M');
		T[k][a].push({c*((k)?-1:1),i});
		T[k][b].push({c*((k)?-1:1),i});
	}
	getpa(1,-1);
	for(int i=1;i<=n;i++){
		for(int j=0;j<2;j++)if(P[i][j])t.addedge(i,n+P[i][j],1);
		t.addedge(0,i,1);
	}
	for(int i=n+1;i<=n+q;i++)t.addedge(i,n+q+1,1);
	t.maxflow(0,n+q+1);
	for(int i=2;i<=n;i++){
		int choose=P[i][0],k=0;
		if(!P[i][0])choose=P[i][1];
		for(auto j:t.go[i]){
			edge x=t.E[j];
			if(x.flow>0){
				choose=P[i][k];
			}
			k++;
			if(k==2)break;
		}
		cout<<i<<" "<<pa[i]<<" "<<val[choose]<<"\n";
	}
}
/*
*/

Compilation message (stderr)

minmaxtree.cpp: In function 'void setIO(std::string)':
minmaxtree.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42