Submission #64463

#	Time	Username	Problem	Language	Result	Execution time	Memory
64463		TadijaSebez	Min-max tree (BOI18_minmaxtree)	C++11	58 / 100	1070 ms	45372 KiB

minmaxtree

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define pb push_back
const int N=70050;
const int M=N*2;
const int inf=1e9+7;
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b){ return a>b?a:b;}
namespace Dinic
{
	int s,t;
	vector<int> G[M];
	struct Edge
	{
		int u,v,c;
		Edge(int a, int b, int d){ u=a,v=b,c=d;}
	};
	vector<Edge> edges;
	void AddEdge(int u, int v, int c)
	{
		G[u].pb(edges.size());
		edges.pb(Edge(u,v,c));
		G[v].pb(edges.size());
		edges.pb(Edge(v,u,0));
	}
	int was[M],dist[M];
	queue<int> q;
	bool BFS()
	{
		int i;
		for(i=s;i<=t;i++) was[i]=0,dist[i]=inf;
		dist[s]=0;
		q.push(s);
		while(q.size())
		{
			int u=q.front();q.pop();
			for(i=0;i<G[u].size();i++)
			{
				int e=G[u][i];
				int v=edges[e].v;
				int c=edges[e].c;
				if(c && dist[v]>dist[u]+1)
				{
					dist[v]=dist[u]+1;
					q.push(v);
				}
			}
		}
		return dist[t]!=inf;
	}
	int Cut(int u, int flow)
	{
		if(u==t) return flow;
		if(dist[u]>dist[t] || !flow) return 0;
		int ans=0;
		for(;was[u]<G[u].size();was[u]++)
		{
			int e=G[u][was[u]];
			int v=edges[e].v;
			int c=edges[e].c;
			if(!c || dist[v]!=dist[u]+1) continue;
			int cut=Cut(v,min(flow,c));
			flow-=cut;
			ans+=cut;
			edges[e].c-=cut;
			edges[e^1].c+=cut;
			if(!flow) return ans;
		}
		return ans;
	}
	int MaxFlow()
	{
		int Flow=0;
		while(BFS()) Flow+=Cut(s,inf);
		return Flow;
	}
}
vector<int> E[N];
int par[N][17],Min[N][17],Max[N][17],dep[N];
void DFS(int u, int p)
{
	int i;
	for(i=0;i<17;i++) Min[u][i]=inf,Max[u][i]=-inf;
	par[u][0]=p;
	dep[u]=dep[p]+1;
	for(i=1;i<17;i++) par[u][i]=par[par[u][i-1]][i-1];
	for(i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(v!=p) DFS(v,u);
	}
}
int LCA(int u, int v)
{
	if(dep[u]<dep[v]) return LCA(v,u);
	int i;
	for(i=16;~i;i--) if(dep[par[u][i]]>=dep[v]) u=par[u][i];
	for(i=16;~i;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
	return v==u?v:par[v][0];
}
void AddMax(int u, int lca, int x)
{
	int i;
	for(i=16;~i;i--)
	{
		if(dep[par[u][i]]>=dep[lca])
		{
			Max[u][i]=max(Max[u][i],x);
			u=par[u][i];
		}
	}
}
void AddMin(int u, int lca, int x)
{
	int i;
	for(i=16;~i;i--)
	{
		if(dep[par[u][i]]>=dep[lca])
		{
			Min[u][i]=min(Min[u][i],x);
			u=par[u][i];
		}
	}
}
void Push(int n)
{
	int j,i;
	for(j=16;j;j--)
	{
		for(i=1;i<=n;i++)
		{
			Max[i][j-1]=max(Max[i][j-1],Max[i][j]);
			Max[par[i][j-1]][j-1]=max(Max[par[i][j-1]][j-1],Max[i][j]);
			Min[i][j-1]=min(Min[i][j-1],Min[i][j]);
			Min[par[i][j-1]][j-1]=min(Min[par[i][j-1]][j-1],Min[i][j]);
		}
	}
}
map<int,int> id;
int sol[N],weg[N];
int main()
{
	int n,i,u,v,m,z,c;char t;
	scanf("%i",&n);
	for(i=1;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
	DFS(1,0);
	scanf("%i",&m);
	for(i=1;i<=m;i++)
	{
		scanf("\n%c %i %i %i",&t,&u,&v,&z);
		id[z]=i;weg[i]=z;
		int lca=LCA(u,v);
		if(t=='M') AddMin(u,lca,z),AddMin(v,lca,z);
		else AddMax(u,lca,z),AddMax(v,lca,z);
	}
	Push(n);
	Dinic::s=0;
	Dinic::t=n+m+1;
	for(i=1;i<=n;i++)
	{
		sol[i]=1;
		Dinic::AddEdge(Dinic::s,i,1);
		if(id.count(Min[i][0])) Dinic::AddEdge(i,id[Min[i][0]]+n,1),sol[i]=Min[i][0];
		if(id.count(Max[i][0])) Dinic::AddEdge(i,id[Max[i][0]]+n,1),sol[i]=Max[i][0];
	}
	for(i=1;i<=m;i++) Dinic::AddEdge(i+n,Dinic::t,1);
	Dinic::MaxFlow();
	for(i=0;i<Dinic::edges.size();i++)
	{
		u=Dinic::edges[i].u;
		v=Dinic::edges[i].v;
		c=Dinic::edges[i].c;
		if(!c && u>0 && u<=n && v>n && v<=n+m)
		{
			sol[u]=weg[v-n];
		}
	}
	for(i=2;i<=n;i++) printf("%i %i %i\n",i,par[i][0],sol[i]);
	return 0;
}

Compilation message (stderr)

minmaxtree.cpp: In function 'bool Dinic::BFS()':
minmaxtree.cpp:41:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<G[u].size();i++)
            ~^~~~~~~~~~~~
minmaxtree.cpp: In function 'int Dinic::Cut(int, int)':
minmaxtree.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;was[u]<G[u].size();was[u]++)
        ~~~~~~^~~~~~~~~~~~
minmaxtree.cpp: In function 'void DFS(int, int)':
minmaxtree.cpp:91:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].size();i++)
          ~^~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:172:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<Dinic::edges.size();i++)
          ~^~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
minmaxtree.cpp:149:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
minmaxtree.cpp:151:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&m);
  ~~~~~^~~~~~~~~
minmaxtree.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%c %i %i %i",&t,&u,&v,&z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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