Submission #502262

#	Time	Username	Problem	Language	Result	Execution time	Memory
502262		PiejanVDC	Keys (IOI21_keys)	C++17	37 / 100	3059 ms	21080 KiB

keys

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

vector<int> find_reachable(vector<int>r, vector<int>u, vector<int>v, vector<int>c) {
    const int n = (int)r.size();
    const int m = (int)u.size();
    int ans[n];
    memset(ans,0,sizeof(ans));
    int mn = INT_MAX;
    vector<pair<int,int>>adj[n];
    for(int i = 0 ; i < m ; i++) {
        adj[u[i]].push_back({v[i],c[i]});
        adj[v[i]].push_back({u[i],c[i]});
    }
    for(int s = 0 ; s < n ; s++) {
        map<int,vector<int>>mp;
        map<int,bool>got;
        queue<int>q;
        q.push(s);
        bool vis[n];
        int sz = 0;
        memset(vis,0,sizeof(vis));
        vis[s] = 1;
        while(!q.empty()) {
            int room = q.front();
            q.pop();
            got[r[room]] = 1;
            sz++;
            for(auto nxt : adj[room]) {
                if(vis[nxt.first]) continue;
                if(got[nxt.second]) {
                    vis[nxt.first] = 1;
                    q.push(nxt.first);
                } else mp[nxt.second].push_back(nxt.first);
            }
            vector<int>res = mp[r[room]];
            mp[r[room]].clear();
            for(auto z : res)
                if(!vis[z]) q.push(z),vis[z]=1;
        }
        if(sz < mn) {
            memset(ans,0,sizeof(ans));
            ans[s] = 1;
            mn = sz;
        } else if(sz == mn) ans[s] = 1;
    }
    vector<int>ret(n);
    for(int i = 0 ; i < n ; i++) ret[i] = ans[i];
    return ret;
}
/*
//#include "keys.h"
#include <cassert>
#include <cstdio>
// BEGIN SECRET
#include <string>
// END SECRET

int main() {
    // BEGIN SECRET
    const std::string input_secret = "xVPHhgQS9btZF57s4vEoQhd6CQPdpE8GWf";
    const std::string output_secret = "Ia5BbhHWUaqX58JkCdhOSt";
    char secret[1000];
    assert(1 == scanf("%s", secret));
    if (std::string(secret) != input_secret) {
        printf("%s\n", output_secret.c_str());
        printf("PV\n");
        printf("Possible tampering with the input\n");
        fclose(stdout);
        return 0;
    }
    // END SECRET
    int n, m;
    assert(2 == scanf("%d%d", &n, &m));
    std::vector<int> r(n), u(m), v(m), c(m);
    for(int i=0; i<n; i++) {
        assert(1 == scanf("%d", &r[i]));
    }
    for(int i=0; i<m; i++) {
        assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
    }
    fclose(stdin);

    std::vector<int> ans = find_reachable(r, u, v, c);

    // BEGIN SECRET
    //printf("%s\n", output_secret.c_str());
    if (int(ans.size()) != n) {
        printf("WA\nReturned array is of the wrong size (len=%d).\n", (int)ans.size());
        return 0;
    }
    for(int i=0; i< (int) ans.size(); i++) {
        if(ans[i]!=0 and ans[i]!=1) {
            printf("WA\nans[%d] should be 0 or 1.\n", i);
            return 0;
        }
    }
    printf("OK\n");
    // END SECRET
    for (int i = 0; i < (int) ans.size(); ++i) {
        if(i) putchar(' ');
        putchar(ans[i]+'0');
    }
    printf("\n");
    return 0;
}
*/

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