Submission #410320

#	Time	Username	Problem	Language	Result	Execution time	Memory
410320		Antekb	Simurgh (IOI17_simurgh)	C++14	0 / 100	1 ms	204 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> U, V;
map<vector<int>, int> M;
int count(vector<int> v){
//cout<<v.size()<<"\n";
	assert(v.size()==n-1);
	sort(v.begin(), v.end());
	if(M.find(v)==M.end()) M[v]=count_common_roads(v);
	return M[v];
}
vector<int> r;
int find(int v){
	if(v==r[v])return v;
	return r[v]=find(r[v]);
}
void Union(int u, int v){
	r[u]=v;
}
int spe;
vector<int> V2[505];
vector<int> span(vector<int> &kol){
	r.resize(n);
	iota(r.begin(), r.end(), 0);
	vector<int> ans;
	for(int i:kol){
		//cout<<U[i]<<" "<<V[i]<<endl;
		int u=find(U[i]), v=find(V[i]);
		if(U[i]==spe)V2[v].push_back(i);
		else if(V[i]==spe)V2[u].push_back(i);
		else if(u!=v){
			Union(u, v);
			ans.push_back(i);
		}
	}
	return ans;
}
vector<int> dobre;
std::vector<int> find_roads(int _n, std::vector<int> u2, std::vector<int> v2) {
	U=u2;
	V=v2;
	n=_n;
	int m=U.size();
	vector<int> edg(m);
	iota(edg.begin(), edg.end(), 0);
	for(int i=0; i<n; i++){
		int k=edg.size()-1;
		for(int j=0; j<k; j++){
			if(U[edg[j]]==i || V[edg[j]]==i){
				while(k>=0 && (U[edg[k]]==i || V[edg[k]]==i))k--;
				if(j>k)break;
				swap(edg[j], edg[k]);
			}
		}
		spe=i;
		for(int j=0; j<n; j++)V2[j].clear();
		vector<int> tre=span(edg);
		/*bool b=1;
		for(int j=0; j<tre.size()-1; j++){
			if((U[tre[j]]==i || V[tre[j]]==i)){
				swap(tre[j], tre.back());
			}
		}
		for(int j=0; j<tre.size()-1; j++){
			if((U[tre[j]]==i || V[tre[j]]==i)){
				b=0;
			}
		}
		if(b){*/
		//cout<<i<<" a"<<endl;
		vector<int> gdzie;
		for(int j=0; j<n; j++){
			if(V2[j].size()){
				//cout<<"b";
				gdzie.push_back(j);
				tre.push_back(V2[j].back());
			}
		}
		//cout<<tre.size()<<"\n";
		for(int k=0; k<gdzie.size(); k++){
			vector<int> ans;
			int M=0;
			//cout<<tre[0]<<" "<<tre[1]<<" "<<tre[2]<<" "<<tre[3]<<" b\n";
			for(int j:V2[gdzie[k]]){
			//cout<<n-1-k<<"\n";
				if(U[j]==i || V[j]==i){
					tre[n-2-k]=j;
					//cout<<tre[0]<<" "<<tre[1]<<" "<<tre[2]<<"\n";
					ans.push_back(count(tre));
					M=max(M, ans.back());
					//cout<<j<<" "<<ans.back()<<"\n";
				}
			}
			int cnt=0;
			deque<int> todo;
			for(int j:V2[gdzie[k]]){
				//if(U[edg[j]]==i || V[edg[j]]==i){
					if(ans[cnt]<M){
						todo.push_back(j);
						//cout<<todo.back()<<"q ";
					}
					cnt++;
				//}
			}
			vector<int> edg2;
			for(int j=0; j<edg.size(); j++){
				if(todo.size() && edg[j]==todo.front()){
					todo.pop_front();
				}
				else edg2.push_back(edg[j]);
			}
			edg=edg2;
			//cout<<"\n";
		}
	}
	//for(int j:edg)cout<<j<<" ";
	assert(edg.size()==n-1);
	
	return edg;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'int count(std::vector<int>)':
simurgh.cpp:9:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    9 |  assert(v.size()==n-1);
      |         ~~~~~~~~^~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:82:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int k=0; k<gdzie.size(); k++){
      |                ~^~~~~~~~~~~~~
simurgh.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    for(int j=0; j<edg.size(); j++){
      |                 ~^~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp:119:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |  assert(edg.size()==n-1);
      |         ~~~~~~~~~~^~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30