Submission #1117917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117917		nai0610	Sphinx's Riddle (IOI24_sphinx)	C++17	0 / 100	47 ms	584 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>

#define ll int64_t
#define ld long double
using namespace std;
// 
const int maxn =1e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
struct Dsu{
	vector<int> par;
	void init(int n){
		par.resize(n+5,0);
		for (int i=1;i<=n;i++) par[i]=i;
	}
	int find (int v){
		if (par[v]==v) return v;
		return par[v]=find(par[v]);
	}
	bool join(int u,int v){
		if ((u = find(u))==(v=find(v))) return false;
		par[v]=u;
		return true;
	} 
} dsu;
vector<int> find_colours(int n,vector<int> x,vector<int> y) {
	dsu.init(n);
	vector<vector<int>> g(n);
	for (int i=0;i<x.size();i++) g[y[i]].push_back(x[i]);
	auto nai =[&](vector<int> v,int c) {
		int res=count(v.begin(),v.end(),c);
		Dsu cnt;cnt.init(n);
		for (int i=0;i<x.size();i++) {
			if (v[x[i]]==c&&v[y[i]]==c) res-=cnt.join(x[i],y[i]);
		}
		return res;
	};
	for (int i=0;i<n;i++) {
		map<int,int> m;
		for (auto j:g[i]) m[dsu.find(j)]=j;
		if (m.size()==0) continue;
		vector<int> v;
		for (auto j:m) v.push_back(j.second);
		auto f =[&](int l,int r){
			vector<int> u={i};
			for (int j=l;j<r;j++) u.push_back(v[j]);
			vector<int> w(n,n);
			for (auto j:u) w[j]=-1;
			return perform_experiment(w)-nai(w,n);
		};
		for (int j=0;j<v.size();j++) {
			if (f(j,v.size())==v.size()-j+1) break;
			int l=j,r=v.size();
			while (l<=r) {
				int mid = (l+r)/2;
				if (f(j,mid)==mid-j+1) l=mid+1;
				else r=mid-1;
			}
			dsu.join(v[l-1],i);
			j=l;
		}
	}
	vector<vector<int>> adj(n);
	for (int i=0;i<x.size();i++) {
		int u =dsu.find(x[i]);
		int v =dsu.find(y[i]);
		if (u!=v) {
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
	}
	vector<vector<int>> comp(n);
	for (int i=0;i<n;i++) comp[dsu.find(i)].push_back(i);
	int r=dsu.find(0);
	vector<int> ord[2];
	vector<int> h(n),vs(n);
	queue<int> q;
	q.push(r);
	vs[r]=1;
	while (!q.empty()) {
		int u= q.front();q.pop();
		ord[h[u]%2].push_back(u);
		for (auto v:adj[u]){
			if (!vs[v]) {
				vs[v]=1;
				h[v]=h[u]+1;
				q.push(v);
			}
		}
	}
	vector<int> res(n,0);
	if (comp[r].size()==n) {
		for (int i=0;i<n;i++) {
			vector<int> v(n,i);
			v[0]=-1;
			if (perform_experiment(v)==1) {
				for (auto j:comp[r]) res[j]=i;
				break;
			}
		}
		return res;
	}
	for (int i=0;i<2;i++) {
		auto f =[&](int c,int l,int r){
			vector<int> v(n,c);
			for (int j=0;j<n;j++) {
				if (!comp[j].empty()&&h[j]%2==i) {
					for (auto k:comp[j]) v[k]=n;
				}
			}
			for (int j=l;j<r;j++) {
				for (auto k:comp[ord[i][j]]) v[k]=-1;
			}
			return perform_experiment(v)-nai(v,c)-nai(v,n)<(r-l);			
		};
		for (int j=1;j<n;j++) {
			vector<int> a;
			for (int k=0;k<ord[i].size();) {
				if (!(f(j,k,ord[i].size()))) break;
				int l=k,r=ord[i].size();
				while (l<=r) {
					int mid =(l+r)/2;
					if (f(j,k,mid)==mid-k+1) l=mid+1;
					else r=mid-1;
				}
				for (auto u:comp[ord[i][l-1]]) res[u]=j;
				a.push_back(l-1);
				k=l;
			}
			reverse(a.begin(),a.end());
			for (auto x:a) ord[i].erase(ord[i].begin()+x);
		}
	}
	return res;
}

Compilation message (stderr)

sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i=0;i<x.size();i++) g[y[i]].push_back(x[i]);
      |               ~^~~~~~~~~
sphinx.cpp: In lambda function:
sphinx.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i=0;i<x.size();i++) {
      |                ~^~~~~~~~~
sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int j=0;j<v.size();j++) {
      |                ~^~~~~~~~~
sphinx.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    if (f(j,v.size())==v.size()-j+1) break;
      |        ~~~~~~~~~~~~~^~~~~~~~~~~~~~
sphinx.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int i=0;i<x.size();i++) {
      |               ~^~~~~~~~~
sphinx.cpp:94:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |  if (comp[r].size()==n) {
      |      ~~~~~~~~~~~~~~^~~
sphinx.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    for (int k=0;k<ord[i].size();) {
      |                 ~^~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36