Submission #1049689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049689		nisanduu	Keys (IOI21_keys)	C++17	20 / 100	3071 ms	32384 KiB

keys

#include <vector>
#include <bits/stdc++.h>

using namespace std;
typedef int ll;
ll dfs(ll node,vector<ll> &vis,vector<vector<ll>> &adj){
    if(vis[node]) return 0;
    vis[node]=1;
    int am = 1;
    for(auto el:adj[node]){
        if(!vis[el]){
            //vis[el]=1;
            am += dfs(el,vis,adj);
        }
    }
    return am;
}

ll dfs2(int node,vector<int> r, vector<int> u, vector<int> v, vector<int> c,vector<vector<pair<ll,ll>>> adj){
    stack<int> st;
	set<pair<ll,ll>> paths;
	map<ll,ll> keys;
	map<ll,ll> visitedNodes;
	keys[r[node]] = 1;
	
	st.push(node);
	int ans = 0;
	while(!st.empty()){
	    ll nnode = st.top();
	    st.pop();
	    if(visitedNodes[nnode]) continue;
	    keys[r[nnode]]=1;
	    ans++;
	    visitedNodes[nnode]=1;
	   
	    
	    for(auto el:adj[nnode]){
	        if(visitedNodes[el.first]) continue;
	        if(!visitedNodes[el.first] && keys[el.second]>0){
	            st.push(el.first);
	        }else{
	            paths.insert({el.first,el.second});
	        }
	    }
	    set<pair<ll,ll>> npaths;
	    for(auto el:paths){
	        if(visitedNodes[el.first]) continue;
	        if(keys[el.second]){
	            st.push(el.first);
	        }else{
	            npaths.insert({el.first,el.second});
	        }
	    }
	    paths = npaths;
	}
	return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	vector<int> ans(r.size(), 0);
	int n = r.size();
	int m = v.size();
	vector<vector<pair<ll,ll>>> adj(n+2);
	for(ll i=0;i<m;i++){
	    adj[v[i]].push_back({u[i],c[i]});
	    adj[u[i]].push_back({v[i],c[i]});
	}
	int mini = 1e9;
	int type = c[0];
	
// 	for(int i=0;i<n;i++){
// 	    if(r[i]==type) {
// 	        vector<ll> vis(n+2);
// 	        ans[i] = dfs(i,vis,adj);
// 	    }else{
// 	        ans[i] = 1;
// 	    }
// 	    mini = min(mini,ans[i]);
	    
// 	}
	
	for(int i=0;i<n;i++){
	    ans[i] = dfs2(i,r,u,v,c,adj);
	    mini = min(ans[i],mini);
	}

	
    for(int i=0;i<n;i++) ans[i] = ans[i]==mini ? 1 : 0;
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:69:6: warning: unused variable 'type' [-Wunused-variable]
   69 |  int type = c[0];
      |      ^~~~

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