Submission #624586

#	Time	Username	Problem	Language	Result	Execution time	Memory
624586		Icebear16	Parachute rings (IOI12_rings)	C++14	0 / 100	250 ms	53052 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) a.size()
int N;
vector<int> adj[1000000];
vector<int> vis(1000000);
void Init(int N_) {

  N = N_;

}

void Link(int A, int B) {
	adj[A].pb(B);
	adj[B].pb(A);
}
int y=0;
bool dfs(int u){
	if(vis[u]) return false;
	y++;
	vis[u]=true;
	if(vis[adj[u][0]] and vis[adj[u][1]]) return true;
	for(int i=0;i<adj[u].size();i++){
		int v=adj[u][i];
		if(!vis[v]){
			dfs[v];
		}
	}
}

int CountCritical(){
	vector<int> v;
	v.clear();
	for(int i=0;i<N;i++){
		if(sz(adj[i])>=2){
			v.pb(i);
		}
	}
	if(sz(v)>2) return 0;
	else if(sz(v)==0){
		int k=0;
		for(int i=0;i<N;i++){
			if(!vis[i]){
				if(dfs[i]) k++;
			}
		}
		if(k>1) return 0;
		else if(k==1) return y;
		else return N;
	}
	else if(sz(v)==1) return 1;
	else{
		int h=sz(adj[v[0]]);
		int l=sz(adj[v[1]]);
		bool temp=false;
		if(h==3 or l==3){
			for(int i=0;i<sz(adj[v[0]]);i++){
				if(adj[v[0]][i]==v[1]){
					temp=true;
					break;
				}
			}
			if(temp==true){
				if(h==3 and l==3) return 2;
				else return 1;
			}
		}
		if(temp==false) return 0;
	}
}

Compilation message (stderr)

rings.cpp: In function 'bool dfs(int)':
rings.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0;i<adj[u].size();i++){
      |              ~^~~~~~~~~~~~~~
rings.cpp:27:9: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   27 |    dfs[v];
      |         ^
rings.cpp:27:9: warning: value computed is not used [-Wunused-value]
   27 |    dfs[v];
      |    ~~~~~^
rings.cpp:27:9: warning: statement has no effect [-Wunused-value]
rings.cpp: In function 'int CountCritical()':
rings.cpp:45:13: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   45 |     if(dfs[i]) k++;
      |             ^
rings.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int i=0;i<sz(adj[v[0]]);i++){
      |                 ^
rings.cpp: In function 'bool dfs(int)':
rings.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^
rings.cpp: In function 'int CountCritical()':
rings.cpp:33:14: warning: control reaches end of non-void function [-Wreturn-type]
   33 |  vector<int> v;
      |              ^

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