제출 #410339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410339		Antekb	Simurgh (IOI17_simurgh)	C++14	51 / 100	722 ms	30984 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> U, V;
map<vector<int>, int> M;
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;
}

bool check(vector<int> v){
	R.resize(n);
	iota(R.begin(), R.end(), 0);
	if(v.size()!=n-1)return 0;
	for(int i:v){
		int u=find(U[i]), v=find(V[i]);
		if(u==v)return 0;
		Union(u ,v);
	}
	return 1;
}
int count(vector<int> v){
	//cout<<v.size()<<"\n";
	assert(check(v));
	sort(v.begin(), v.end());
	if(M.find(v)==M.end()) M[v]=count_common_roads(v);
	return M[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){
			//cout<<u<<" "<<v<<"w\n";
			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]<<" "<<" b\n";
			for(int j:V2[gdzie[k]]){
				//cout<<j<<"\n";
				if(U[j]==i || V[j]==i){
					tre[n-1-gdzie.size()+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);
	assert(count(edg)==n-1);
	sort(edg.begin(), edg.end());
	return edg;
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'bool check(std::vector<int>)':
simurgh.cpp:19:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |  if(v.size()!=n-1)return 0;
      |     ~~~~~~~~^~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int k=0; k<gdzie.size(); k++){
      |                ~^~~~~~~~~~~~~
simurgh.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    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:132:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |  assert(edg.size()==n-1);
      |         ~~~~~~~~~~^~~~~

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