Submission #535223

#	Time	Username	Problem	Language	Result	Execution time	Memory
535223		Icebear16	Keys (IOI21_keys)	C++17	0 / 100	1 ms	460 KiB

keys

#include <bits/stdc++.h>
//try using an edge list instead of an adjacency list
std::vector<int> adj[3000];
std::vector<int> Adj[3000];
std::vector<int> temp[3000];
std::vector<bool> visited(3000,false);
int k=0;
std::set<int> s;
void dfs(int n, std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c){
	if(visited[n]){
		return;
	}else{
		visited[n]=true;
		std::cout<<n<<std::endl;
		s.insert(r[n]);
		k+=1;
	}
//	for(int i=0;i<r.size();i++){
//		Adj[i]=temp[i];
//	}
	for(int i=0;i<u.size();i++){
		if(u[i]==n){
			Adj[v[i]].push_back(c[i]);
			std::cout<<n<<" "<<v[i]<<" "<<c[i]<<std::endl;
		}
		if(v[i]==n){
			Adj[u[i]].push_back(c[i]);
			std::cout<<n<<" "<<u[i]<<" "<<c[i]<<std::endl;
		}
	}
	for(int i=0;i<adj[n].size();i++){
		int y=adj[n][i];
		for(int j=0;j<Adj[y].size();j++){
//			if((u[j]==n && v[j]==y) || (v[j]==n && u[j]==y)){
				if(s.count(Adj[y][j])==1){
					dfs(y,r,u,v,c);
					break;
				}
//			}
		}
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	std::vector<int> ans(r.size(), 1);
	for(int i=0;i<u.size();i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	for(int i=0;i<r.size();i++){
		std::cout<<"pi"<<i<<std::endl;
		for(int j=0;j<r.size();j++){
			s.erase(j);
		}
		s.insert(r[i]);
		dfs(i,r,u,v,c);
		std::cout<<k<<std::endl;
		ans[i]=k;
		k=0;
		for(int j=0;j<r.size();j++){
			visited[j]=false;
		}
	}
	int m=1000000;
	for(int i=0;i<r.size();i++){
		m=std::min(m,ans[i]);
	}
//	return ans;
	for(int i=0;i<r.size();i++){
		if(ans[i]==m){
			ans[i]=1;
		}else{
			ans[i]=0;
		}
	}
	return ans;
}

//output
//0 1 1 0

//input
//4 5
//0 1 1 0
//0 1 0
//0 2 0
//1 2 0
//1 3 0
//3 1 0

//output
//0 1 1 0

//input
//4 5
//0 1 1 2
//0 1 0
//0 2 0
//1 2 1
//1 3 0
//3 1 2

//#include <bits/stdc++.h>
//std::vector<int> adj[3000];
//std::vector<bool> visited(3000,false);
//int k=0;
//std::set<int> s;
//void dfs(int n, std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c){
//	if(visited[n]){
//		return;
//	}else{
//		visited[n]=true;
//		s.insert(r[n]);
//		k+=1;
//	}
//	for(int i=0;i<adj[n].size();i++){
//		int y=adj[n][i];
//		for(int j=0;j<u.size();j++){
//			if((u[j]==n && v[j]==y) || (v[j]==n && u[j]==y)){
//				if(s.count(c[j])==1){
//					dfs(y,r,u,v,c);
//				}
//			}
//		}
//	}
//}
// 
//std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
//	std::vector<int> ans(r.size(), 1);
//	for(int i=0;i<u.size();i++){
//		adj[u[i]].push_back(v[i]);
//		adj[v[i]].push_back(u[i]);
//	}
//	for(int i=0;i<r.size();i++){
//		for(int j=0;j<r.size();j++){
//			s.erase(j);
//		}
//		s.insert(r[i]);
//		dfs(i,r,u,v,c);
//		ans[i]=k;
//		k=0;
//		for(int j=0;j<r.size();j++){
//			visited[j]=false;
//		}
//	}
//	int m=1000000;
//	for(int i=0;i<r.size();i++){
//		m=std::min(m,ans[i]);
//	}
//	for(int i=0;i<r.size();i++){
//		if(ans[i]==m){
//			ans[i]=1;
//		}else{
//			ans[i]=0;
//		}
//	}
//	return ans;
//}

Compilation message (stderr)

keys.cpp: In function 'void dfs(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<u.size();i++){
      |              ~^~~~~~~~~
keys.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=0;i<adj[n].size();i++){
      |              ~^~~~~~~~~~~~~~
keys.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j=0;j<Adj[y].size();j++){
      |               ~^~~~~~~~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<u.size();i++){
      |              ~^~~~~~~~~
keys.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~
keys.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int j=0;j<r.size();j++){
      |               ~^~~~~~~~~
keys.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int j=0;j<r.size();j++){
      |               ~^~~~~~~~~
keys.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~
keys.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33