Submission #1170945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170945		user736482	Meetings (JOI19_meetings)	C++20	29 / 100	606 ms	796 KiB

meetings

#include "meetings.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353
#define POT 4194304
#define INF 1000000019
#define INFL 1000000000000000099LL
#define STALA 3
random_device rd;
mt19937 g(rd());
vector<ll>dzieci[2007],dzieci2[2007];
ll sz[2007],sz2[2007];

ll fnd(ll x,ll y){
	for(ll i=0;i<2007;i++){
		//	dzieci2[i]=dzieci[i];
	//		sz2[i]=sz[i];	
		}
		ll pom=x;
		ll ak=y;
		sz[ak]++;
		vector<ll>odw;
			vector<pair<ll,ll>>v;
			for(ll i=0;i<dzieci[ak].size();i++){
				v.pb({sz[dzieci[ak][i]],dzieci[ak][i]});
			}
			sort(v.begin(),v.end());
			
			for(ll j=0;j<=v.size();j++){
				if(j==v.size()){
					return y;
					//sz[ak]++;
				//	dzieci[ak].pb(pom);
					//sz[pom]=1;
					//ak=2006;
					//break;
				}
				if(v[j].ff>sz[ak]/STALA){
					ll pom=fnd(x,v[j].ss);
					if(pom!=v[j].ss){
						return pom;
					}
					else{
						ll pom2=Query(pom,x,y);
						if(pom2==y){
						//	sz[y]--;
						//	return y;
						continue;
						}
						else if(pom2==pom){
							return pom;
						}
						else if(pom2==x){
							ll pom2=v[j].ss;
							dzieci[ak].erase(find(dzieci[ak].begin(),dzieci[ak].end(),v[j].ss));
							//dzieci[ak].pb(pom);
							dzieci[x].pb(pom2);
							sz[x]=sz[pom2];
							//sz[ak]++;
							return ak;
						//	ak=2006;
						//	break;
						}
						ll pom3=v[j].ss;
						dzieci[ak].erase(find(dzieci[ak].begin(),dzieci[ak].end(),v[j].ss));
						dzieci[ak].pb(pom2);
						//dzieci[ans].pb(pom);
						dzieci[pom2].pb(pom3);
						sz[pom2]=sz[pom3]+1;
					//	sz[pom]=1;
						sz[ak]+=2;
						for(ll k : odw)
							sz[k]++;
						//ak=2006;
						return pom2;
						
					}
				}
				ll ans=Query(pom,v[j].ss,ak);
				if(ans==pom){
					ll pom2=v[j].ss;
					dzieci[ak].erase(find(dzieci[ak].begin(),dzieci[ak].end(),v[j].ss));
					//dzieci[ak].pb(pom);
					dzieci[pom].pb(pom2);
					sz[pom]=sz[pom2];
					//sz[ak]++;
					return ak;
				//	ak=2006;
				//	break;
				}
				if(ans==ak)
					continue;
				if(ans==v[j].ss){
					sz[ak]++;
					return fnd(pom,v[j].ss);
				//	ak=v[j].ss;
					//break;
				}
				ll pom2=v[j].ss;
				dzieci[ak].erase(find(dzieci[ak].begin(),dzieci[ak].end(),v[j].ss));
				dzieci[ak].pb(ans);
				//dzieci[ans].pb(pom);
				dzieci[ans].pb(pom2);
				sz[ans]=sz[pom2]+1;
			//	sz[pom]=1;
				sz[ak]+=2;
				for(ll k : odw)
					sz[k]++;
				//ak=2006;
				return ans;
				//break;
			}
		//	odw.pb(ak);
		//if(ak!=2006)
		//	dzieci[ak].pb(pom);
	//return y;

}

void Solve(int n){
	vector<ll>dodod;
	for(ll i=1;i<n;i++){
		dodod.pb(i);
	}
	shuffle(dodod.begin(),dodod.end(),rd);
	sz[0]=1;
	while(dodod.size()){
		//cout<<"\n\n";
		//for(ll i=0;i<n;i++){
		//	for(ll j : dzieci[i])
		//		cout<<i<<" "<<j<<"\n";
		//}cout<<"\n\n";
		if(sz[dodod.back()]){
			dodod.pop_back();
			continue;
		}
		ll pom=fnd(dodod.back(),0);
		sz[pom]++;
		dzieci[pom].pb(dodod.back());
		sz[dodod.back()]++;
		dodod.pop_back();
	}
	for(ll i=0;i<n;i++){
		for(ll j : dzieci[i])
			Bridge(min(i,j),max(i,j));
	}
}

Compilation message (stderr)

meetings.cpp: In function 'long long int fnd(long long int, long long int)':
meetings.cpp:124:1: warning: control reaches end of non-void function [-Wreturn-type]
  124 | }
      | ^

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71