Submission #819953

#	Time	Username	Problem	Language	Result	Execution time	Memory
819953		Marco_Escandon	Keys (IOI21_keys)	C++17	37 / 100	3045 ms	43644 KiB

keys

#include "keys.h"
#include <cassert>
#include <cstdio>

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<ll,ll>>> cad;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v1, std::vector<int> c)
{
    ll n=r.size();
    ll m=u.size();cad.resize(n*2+1);
    for(int i=0; i<m; i++){
        cad[u[i]].push_back({v1[i],c[i]});
        cad[v1[i]].push_back({u[i],c[i]});
    }
    ll bs=n+3;
    vector<int> sol(n,0);
    for(int i=0; i<n; i++)
    {
        vector<ll> v(n*2,0),lla(n*2,0);
        vector<vector<ll>> ca(n*2+1);
        queue<ll> q;
        q.push(i);
        while(!q.empty())
        {
            ll a=q.front();q.pop();
            if(v[a]==0)
            {
                v[a]=2;
                lla[r[a]]=1;
                for(auto j:ca[r[a]])
                {
                    q.push(j);
                }
                ca[r[a]].clear();
                for(auto j:cad[a])
                {
                    if(lla[j.second]==1)
                    {
                        q.push(j.first);
                    }
                    ca[j.second].push_back(j.first);
                }
            }
        }
        ll cont=0;
        for(auto j:v)
        {
            if(j==2)
                cont++;
            //cout<<j<<" ";
        }
        //cout<<"\n";
        sol[i]=cont;
        bs=min(bs,cont);
    }
    for(int i=0; i<n; i++)
        if(sol[i]==bs)
            sol[i]=1;
        else sol[i]=0;
    return sol;
}

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