제출 #814235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
814235		PixelCat	열쇠 (IOI21_keys)	C++17	37 / 100	105 ms	16848 KiB

keys

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 2000;
const int MAXK = 2000;

vector<pii> adj[MAXN + 10];

int vis[MAXN + 10];
int ok[MAXK + 10];
vector<int> ed[MAXK + 10];

int solve(int n, int s, vector<i32> &R) {
    For(i, 0, n - 1) {
        vis[i] = ok[i] = 0;
        ed[i].clear();
    }

    queue<int> quer, quek;
    quer.emplace(s);
    vis[s] = 1;
    while(sz(quer) || sz(quek)) {
        if(sz(quer)) {
            int cur = quer.front(); quer.pop();
            if(!ok[R[cur]]) {
                ok[R[cur]] = 1;
                quek.emplace(R[cur]);
            }
            for(auto &e:adj[cur]) {
                if(ok[e.S] && !vis[e.F]) {
                    vis[e.F] = 1;
                    quer.emplace(e.F);
                } else if(!ok[e.S]) {
                    ed[e.S].eb(e.F);
                }
            }
        }
        if(sz(quek)) {
            int k = quek.front(); quek.pop();
            for(auto &i:ed[k]) if(!vis[i]) {
                vis[i] = 1;
                quer.emplace(i);
            }
            ed[k].clear();
        }
    }

    int cnt = 0;
    For(i, 0, n - 1) if(vis[i]) cnt++;
    return cnt;
}

vector<i32> find_reachable(vector<i32> R, vector<i32> U, vector<i32> V, vector<i32> C) {
    int n = sz(R);
    int m = sz(C);
    
    For(i, 0, m - 1) {
        adj[U[i]].eb(V[i], C[i]);
        adj[V[i]].eb(U[i], C[i]);
    }
    vector<int> cnt;
    int mn = n + 48763;
    For(i, 0, n - 1) {
        cnt.eb(solve(n, i, R));
        mn = min(mn, cnt.back());
    }
    vector<i32> ans;
    For(i, 0, n - 1) {
        ans.eb(cnt[i] == mn);
    }
    return ans;
}

/*

4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2

0 1 1 0


7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1

0 1 1 0 1 0 1


3 1
0 0 0
0 1 0

0 0 1

*/

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