제출 #1217495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217495		hengliao	열쇠 (IOI21_keys)	C++20	37 / 100	103 ms	8516 KiB

keys

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll inf=1e18;
    const ll mxN=2005;

    ll n, m;

    bool done[mxN];
    vll adj[mxN];
    vector<pll> edges[mxN];
    bool visited[mxN];
    ll siz[mxN];
    ll r[mxN];

    void dfs(ll cur);

    void add_edge(ll x, ll y){
        adj[x].pb(y);
        adj[y].pb(x);
        if(visited[x] && !visited[y]){
            dfs(y);
        }
        else if(visited[y] && !visited[x]){
            dfs(x);
        }
    }

    void dfs(ll cur){
        if(visited[cur]) return;
        visited[cur]=1;
        if(!done[r[cur]]){
            done[r[cur]]=1;
            for(auto &it:edges[r[cur]]){
                add_edge(it.F, it.S);
            }
        }
        for(auto &it:adj[cur]){
            dfs(it);
        }
    }
}

vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) {
	
    n=R.size();
    for(ll i=0;i<n;i++){
        r[i]=R[i];
    }
    m=u.size();

    for(ll i=0;i<m;i++){
        edges[c[i]].pb({u[i], v[i]});
    }

    for(ll i=0;i<n;i++){
        siz[i]=0;
        memset(done, 0, sizeof(done));
        for(ll j=0;j<n;j++){
            adj[j].clear();
        }
        memset(visited, 0, sizeof(visited));
        dfs(i);
        for(ll j=0;j<n;j++){
            if(visited[j]) siz[i]++;
        }
    }

    ll mn=inf;

    for(ll i=0;i<n;i++){
        mn=min(mn, siz[i]);
    }

    vector<int> re(n);
    for(ll i=0;i<n;i++){
        if(mn==siz[i]){
            re[i]=1;
        }
    }

	return re;
}

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