제출 #1049656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049656		nisanduu	열쇠 (IOI21_keys)	C++17	9 / 100	3025 ms	24600 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;
}

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<ll>> adj(n+2);
	for(ll i=0;i<m;i++){
	    adj[v[i]].push_back(u[i]);
	    adj[u[i]].push_back(v[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] = ans[i]==mini ? 1 : 0;
	return ans;
}

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