oj.uz

Submission #69867

# Submission time Handle Problem Language Result Execution time Memory
69867 2018-08-21T17:43:23 Z KLPP Parachute rings (IOI12_rings) C++14
20 / 100
 2214 ms 263168 KB 
#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;
}

Compilation message

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 125560 KB Output is correct
2 Correct 137 ms 157824 KB Output is correct
3 Correct 139 ms 157824 KB Output is correct
4 Correct 113 ms 157824 KB Output is correct
5 Correct 114 ms 157824 KB Output is correct
6 Correct 118 ms 157824 KB Output is correct
7 Correct 134 ms 157824 KB Output is correct
8 Correct 115 ms 157824 KB Output is correct
9 Correct 141 ms 157848 KB Output is correct
10 Correct 148 ms 157848 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 157848 KB Output is correct
2 Runtime error 2214 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 125560 KB Output is correct
2 Correct 137 ms 157824 KB Output is correct
3 Correct 139 ms 157824 KB Output is correct
4 Correct 113 ms 157824 KB Output is correct
5 Correct 114 ms 157824 KB Output is correct
6 Correct 118 ms 157824 KB Output is correct
7 Correct 134 ms 157824 KB Output is correct
8 Correct 115 ms 157824 KB Output is correct
9 Correct 141 ms 157848 KB Output is correct
10 Correct 148 ms 157848 KB Output is correct
11 Runtime error 143 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 125560 KB Output is correct
2 Correct 137 ms 157824 KB Output is correct
3 Correct 139 ms 157824 KB Output is correct
4 Correct 113 ms 157824 KB Output is correct
5 Correct 114 ms 157824 KB Output is correct
6 Correct 118 ms 157824 KB Output is correct
7 Correct 134 ms 157824 KB Output is correct
8 Correct 115 ms 157824 KB Output is correct
9 Correct 141 ms 157848 KB Output is correct
10 Correct 148 ms 157848 KB Output is correct
11 Runtime error 143 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 125560 KB Output is correct
2 Correct 137 ms 157824 KB Output is correct
3 Correct 139 ms 157824 KB Output is correct
4 Correct 113 ms 157824 KB Output is correct
5 Correct 114 ms 157824 KB Output is correct
6 Correct 118 ms 157824 KB Output is correct
7 Correct 134 ms 157824 KB Output is correct
8 Correct 115 ms 157824 KB Output is correct
9 Correct 141 ms 157848 KB Output is correct
10 Correct 148 ms 157848 KB Output is correct
11 Correct 520 ms 157848 KB Output is correct
12 Runtime error 2214 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -