Submission #548427

#	Time	Username	Problem	Language	Result	Execution time	Memory
548427		topovik	Keys (IOI21_keys)	C++17	37 / 100	1014 ms	21296 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
#define pb push_back
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef long double ld;

const ll N = 5e3 + 100;
const ll oo = 1e9;

int col[N];
bool mrk[N];
vector <pair<int, int> > a[N];
vector <int> ps[N];

std::vector<int> find_reachable (std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    int n = r.size();
    int m = u.size();
    for (int i = 0; i < n; i++) col[i] = r[i];
    for (int i = 0; i < m; i++)
    {
        a[u[i]].pb({v[i], c[i]});
        a[v[i]].pb({u[i], c[i]});
    }

    vector <int> ans;
    int mx = oo;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++) mrk[j] = 0, ps[j].clear();
        set<int> st;
        queue <int> q;
        q.push(i);
        mrk[i] = 1;
        int kol = 0;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            if (!st.count(col[x]))
            {
                for (auto i : ps[col[x]])
                    if (!mrk[i])
                {
                    q.push(i);
                    mrk[i] = 1;
                }
            }
            st.insert(col[x]);
            kol++;
            for (auto i : a[x])
                if (!mrk[i.f])
                {
                    if (st.count(i.s))
                    {
                        mrk[i.f] = 1;
                        q.push(i.f);
                    }
                    else ps[i.s].pb(i.f);
                }
        }
        if (kol < mx)
        {
            mx = kol;
            ans.clear();
        }
        if (mx == kol) ans.pb(i);
    }
    vector <int> ans1(n, 0);
    for (auto i : ans) ans1[i] = 1;
    return ans1;
}
//
//int main()
//{
//    ios_base::sync_with_stdio(0);
//    iostream::sync_with_stdio(0);
//    cin.tie(0);
//    int n, m;
//    cin >> n >> m;
//    vector <int> r(n);
//    vector <int> u(m), v(m), c(m);
//    for (int i = 0; i < n; i++) cin >> r[i];
//    for (int i = 0; i < m; i++) cin >> u[i] >> v[i] >> c[i];
//    vector <int> ans = find_reachable(r, u, v, c);
//    for (auto i : ans) cout << i << " ";
//    cout << endl;
//}

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