Submission #535956

#	Time	Username	Problem	Language	Result	Execution time	Memory
535956		Icebear16	Keys (IOI21_keys)	C++17	20 / 100	3077 ms	21752 KiB

keys

#include <bits/stdc++.h>

struct edge{
	int u,v;
	int weight;
     
	  edge(int _u,int _v,int _w){
		 u=_u;
		 v=_v;
		 weight=_w;
	  }
	  
};

std::vector<edge> adj[3000];
std::vector<bool> visited(3000,false);
int k=1;
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].v;
		int f=adj[n][i].weight;
		if(s.count(f)==1 && visited[y]==false){
			k+=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(edge(u[i],v[i],c[i]));
		adj[v[i]].push_back(edge(v[i],u[i],c[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=1;
		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:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<adj[n].size();i++){
      |              ~^~~~~~~~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<u.size();i++){
      |              ~^~~~~~~~~
keys.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~
keys.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int j=0;j<r.size();j++){
      |               ~^~~~~~~~~
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:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~
keys.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~

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