Submission #62000

#	Time	Username	Problem	Language	Result	Execution time	Memory
62000		hamzqq9	Min-max tree (BOI18_minmaxtree)	C++14	0 / 100	1060 ms	208048 KiB

minmaxtree

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define sz(x) (x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000005
#define MOD 1000000007
#define N 70005
#define LOG 20
using namespace std;

struct query {

	int from,to,cost;

	bool operator<(const query& oth) const {

		return cost<oth.cost;

	}

};

vector<query> Max,Min;
int n,q,x,y,z,totnode;
int dis[N],match[N],deep[N],ata[N],der[N],par[N];
vector<int> v[N],v2[N];

int bul(int node) {

	if(ata[node]==node) return node;

	return ata[node]=bul(ata[node]);

}

void dfs(int node) {

	if(node) {

		for(int i:v2[node]) {

			if(dis[node]+1==dis[match[i]]) {

				dfs(match[i]);

				if(dis[match[i]]!=inf) {

					match[node]=i;
					match[i]=node;

					return ;

				}

			}

		}

		dis[node]=inf;

	}

}

bool bfs() {

	queue<int> q;

	for(int i=1;i<=n;i++) {

		if(!match[i]) {

			dis[i]=0;
			q.push(i);

		}
		else dis[i]=inf;

	}

	dis[0]=inf;

	while(!q.empty()) {

		int node=q.front();

		q.pop();

		if(dis[node]<dis[0]) {

			for(int i:v2[node]) {

				if(dis[match[i]]==inf) {

					dis[match[i]]=dis[node]+1;

					q.push(match[i]);

				}

			}

		} 

	}

	return (dis[0]!=inf);

}

void hopcroft_karp() {

	totnode=n+sz(Max)+sz(Min);

	while(bfs()) {

		for(int i=1;i<=totnode;i++) if(!match[i]) dfs(i);

	}

}

void merge(int x,int y) {

	y=bul(y);
	x=bul(x);

	if(rand()&1) swap(x,y);

	deep[y]=min(deep[y],deep[x]);
	ata[x]=y;

}

void make(int node,int from,int to) {

	from=deep[bul(from)];
	to=deep[bul(to)];

	while(from!=to) {

		if(der[from]<der[to]) swap(from,to);

		merge(from,par[from]);

		v2[from].pb(node);
		v2[node].pb(from);

		from=deep[bul(from)];

		if(par[from]==par[to]) {

			merge(from,to);

			break ;

		}

	}

}

void init() {

	for(int i=1;i<=n;i++) {

		deep[i]=i;
		ata[i]=i;

	}

}

void dfs(int node,int ata) {

	par[node]=ata;
	der[node]=der[ata]+1;

	for(int i:v[node]) {

		if(i==ata) continue ;

		dfs(i,node);

	}

}

int main() {

//	freopen("input.txt","r",stdin);

	srand(time(NULL));

	scanf("%d",&n);

	for(int i=1;i<n;i++) {

		scanf("%d %d",&x,&y);

		v[x].pb(y);
		v[y].pb(x);

	}	

	dfs(1,0);

	scanf("%d",&q);

	while(q--) {

		char c;

		scanf(" %c %d %d %d",&c,&x,&y,&z);

		if(c=='m') Min.pb({x,y,z});
		else Max.pb({x,y,z});

	}

	sort(all(Min));
	reverse(all(Min));
	sort(all(Max));

	init();

	for(int i=0;i<sz(Max);i++) make(i+1+n,Max[i].from,Max[i].to);

	init();

	for(int i=0;i<sz(Min);i++) make(i+1+sz(Max)+n,Min[i].from,Min[i].to);

	hopcroft_karp();

	for(int i=2;i<=n;i++) {

		int cst;

		if(match[i]<=n+sz(Max)) cst=Max[match[i]-n-1].cost;
		else cst=Min[match[i]-n-sz(Max)-1].cost;

		printf("%d %d %d\n",i,par[i],cst);

	}

}

Compilation message (stderr)

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:239:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<sz(Max);i++) make(i+1+n,Max[i].from,Max[i].to);
               ^
minmaxtree.cpp:243:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<sz(Min);i++) make(i+1+sz(Max)+n,Min[i].from,Min[i].to);
               ^
minmaxtree.cpp:251:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(match[i]<=n+sz(Max)) cst=Max[match[i]-n-1].cost;
              ^
minmaxtree.cpp:207:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
minmaxtree.cpp:211:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
minmaxtree.cpp:220:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
minmaxtree.cpp:226:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %d %d",&c,&x,&y,&z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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