Submission #819944

#	Time	Username	Problem	Language	Result	Execution time	Memory
819944		Marco_Escandon	Keys (IOI21_keys)	C++17	0 / 100	1 ms	212 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;
vector<vector<ll>> ca;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
    ll n=r.size();
    ll m=u.size();
    ca.resize(n*2+1);cad.resize(n*2+1);
    for(int i=0; i<m; i++){
        cad[u[i]].push_back({v[i],c[i]});
        cad[v[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);
        queue<ll> q;
        v[i]=2;
        q.push(i);
        while(!q.empty())
        {
            ll a=q.front();q.pop();
            lla[r[a]]=1;
            for(auto j:ca[r[a]])
            {
                if(v[j]==0)
                {
                    v[j]=2;
                    q.push(j);
                }
            }
            ca[r[a]].clear();
            for(auto j:cad[a])
            {
                if(v[j.first]==0)
                {
                    if(lla[j.second]==1)
                    {
                        v[j.first]=2;
                        q.push(j.first);
                    }
                    else
                    {
                        ca[j.second].push_back(j.first);
                    }
                }
            }
        }
        ll cont=0;
        for(auto j:v)
            if(j==2)
                cont++;
        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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33