Submission #838792

#	Time	Username	Problem	Language	Result	Execution time	Memory
838792		ErJ	Keys (IOI21_keys)	C++17	9 / 100	3048 ms	30968 KiB

keys

#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;
typedef long long ll;

vector<vector<pair<int, int>>> edges; //kam, key
vector<int> p, r;

vector<vector<int>> kv;//potrebuji klic na hranu vedouci do vrcholu
vector<bool> was;

int DFS(int u) {
    int ans = 0;
    queue<int> q;
    q.push(u);
    was[u] = true;
    kv[r[u]][0] = -2;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int i = 0; i < edges[v].size(); i++) {
            //cout << i << endl;
            int w = edges[v][i].first;
            int kw = edges[v][i].second;
            if (kv[kw][0] == -2) {
                if (!was[w]) {
                    was[w] = true;
                    q.push(w);
                    ans++;
                    if (kv[r[w]][0] != -2) {
                        kv[r[w]][0] = -2;
                        for (int i = 1; i < kv[r[w]].size(); i++) {
                            int x = kv[r[w]][i];
                            if (!was[x]) {
                                was[x] = true;
                                q.push(x);
                                ans++;
                            }
                        }
                    }
                }
            }
            else {
                if(!was[w]) kv[kw].push_back(w);
            }
        }
    }
    return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int n = r.size();
    int m = u.size();
    edges.resize(n);
    for (int i = 0; i < m; i++) {
        edges[u[i]].push_back({ v[i], c[i] });
        edges[v[i]].push_back({ u[i], c[i] });
    }
    p.resize(n);
    ::r = r;
    int MIN = 1000000009;
    //cout << "ahoj" << endl;
    for (int i = 0; i < n; i++) {
        //cout << "ahoj" << i << endl;
        kv.clear();
        was.clear();
        kv.resize(n);
        was.resize(n);
        for (int j = 0; j < n; j++) {
            kv[j].push_back(-1);
            was[j] = false;
        }
        p[i] = DFS(i);
        MIN = min(MIN, p[i]);
    }
    //cout << "ahojda" << endl;
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        //cout << p[i] << endl;
        if (p[i] == MIN) {
            ans[i] = 1;
        }
        else {
            ans[i] = 0;
        }
    }
    return ans;
}

Compilation message (stderr)

keys.cpp: In function 'int DFS(int)':
keys.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int i = 0; i < edges[v].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
keys.cpp:37:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                         for (int i = 1; i < kv[r[w]].size(); i++) {
      |                                         ~~^~~~~~~~~~~~~~~~~

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