제출 #69867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69867		KLPP	낙하산 고리들 (IOI12_rings)	C++14	20 / 100	2214 ms	263168 KiB

rings

#include<iostream>
#include<vector>
#include<queue>
#include<stdio.h>

using namespace std;
class DSU{
	int parent[1000000];
	int size[1000000];
	public:
	void init(int n){
		for(int i=0;i<n;i++){
			parent[i]=i;
			size[i]=1;
		}
	}
	int root(int a){
		if(parent[a]==a)return a;
		parent[a]=root(parent[a]);
		return parent[a];
	}
	void merge(int a, int b){
		a=root(a);
		b=root(b);
		if(a==b)return;
		if(size[a]>size[b]){
			size[a]+=size[b];
			parent[b]=a;
			return;
		}size[b]+=size[a];
		parent[a]=b;
	}
	bool samecomponent(int a, int b){
		return root(a)==root(b);
	}
	
};
class graph1{
	int n;
	vector<int> nei[1000000];
	int cyclesize;
	DSU *D;
	public:
	void init(int N){
		n=N;
		cyclesize=-1;
		D=new DSU();
		D->init(n);
	}
	int insert(int a, int b){
		nei[a].push_back(b);
		nei[b].push_back(a);
		if(nei[a].size()==3){
			return a;
		}
		if(nei[b].size()==3){
			return b;
		}
		if(D->samecomponent(a,b)){
			if(cyclesize!=-1)cyclesize=0;
			else{
				queue<int> q;
				q.push(a);
				bool visited[n];
				for(int i=0;i<n;i++)visited[i]=false;
				cyclesize=0;
				while(!q.empty()){
					int u=q.front();q.pop();
					if(!visited[u]){
						visited[u]=true;cyclesize++;
						for(int i=0;i<nei[u].size();i++){
							q.push(nei[u][i]);
						}	
					}
				}
			}
		}
		D->merge(a,b);
		return -1;
	}
	int query(){
		if(cyclesize==-1)return n;
		return cyclesize;
	}
	void print(){
		for(int i=0;i<n;i++){
			cout<<"Vizinhos de "<<i<<": ";
			for(int j=0;j<nei[i].size();j++)cout<<nei[i][j]<<" ";
			cout<<endl;
		}
	}
	int vizinho(int i, int j){
		return nei[i][j];
	}
};
class graph2{
	int n;
	vector<int> nei[1000000];
	bool B;
	DSU *D;
	int proibido;
	public:
	void init(int N,int f){
		n=N;
		B=true;
		D=new DSU();
		D->init(n);
		proibido=f;
	}
	void insert(int a, int b){
		if(a==proibido || b==proibido)return;
		nei[a].push_back(b);
		nei[b].push_back(a);
		if(nei[a].size()==3){
			B=false;
		}
		if(nei[b].size()==3){B=false;
		}
		if(D->samecomponent(a,b)){
			B=false;
		}D->merge(a,b);
	}
	bool query(){
		return B;
	}
};

int N;
graph1 *G;
vector<pair<int,int> >edges;
int etapa;
graph2 *arr[4];
void Init(int N_) {
	G=new graph1();
	G->init(N_);
	etapa=1;
	N=N_;
	for(int i=0;i<4;i++)arr[i]=new graph2();
}

void Link(int A, int B) {
	edges.push_back(pair<int,int>(A,B));
	if(etapa==1){
		int resposta=G->insert(A,B);
		if(resposta!=-1){
			etapa=2;
			arr[3]->init(N,resposta);
			for(int i=0;i<3;i++){
				arr[i]->init(N,G->vizinho(resposta,i));
			}
			for(int i=0;i<edges.size();i++){
				for(int j=0;j<4;j++){
					arr[j]->insert(edges[i].first,edges[i].second);
				}
			}
		}
	}else{
		for(int j=0;j<4;j++)arr[j]->insert(A,B);
	}
}

int CountCritical() {//G->print();
	if(etapa==1){
		return G->query();
	}
	int ans=0;
	for(int i=0;i<4;i++)ans+=arr[i]->query();
	return ans;
}

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

rings.cpp: In member function 'int graph1::insert(int, int)':
rings.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<nei[u].size();i++){
                   ~^~~~~~~~~~~~~~
rings.cpp: In member function 'void graph1::print()':
rings.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<nei[i].size();j++)cout<<nei[i][j]<<" ";
                ~^~~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:151:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<edges.size();i++){
                ~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31