Submission #1020946

#TimeUsernameProblemLanguageResultExecution timeMemory
1020946mdn2002Keys (IOI21_keys)C++17
Compilation error
0 ms0 KiB
/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int n = r.size(), m = u.size(), st;
    vector<int> vis(n), did(n), p(n);
    vector<vector<pair<int, int>>> gr(n);
    vector<vector<int>> vv(n);

    for (int i = 0; i < m; i ++) {
        gr[u[i]].push_back({v[i], c[i]});
        gr[v[i]].push_back({u[i], c[i]});
    }
    function<void(int)> dfs = [&] (int x) {
        vis[x] = 1, did[r[x]] = 1;
        p[st] ++;
        while (vv[r[x]].size()) {
            int u = vv[r[x]].back();
            vv[r[x]].clear();
            dfs(u);
        }
        for (auto [u, c] : gr[x]) {
            if (vis[u]) continue;
            if (did[c]) dfs(u);
            else vv[c].push_back(u);
        }
    };
    int mn = 1e9;
    for (int i = 0; i < n; i ++) {
        vis.assign(n, 0);
        did.assign(n, 0);
        st = i;
        dfs(i);
        for (int j = 0; j < n; j ++) vv[j].clear();
        mn = min(mn, p[i]);
    }
    vector ans(n, 0);
    for (int i = 0; i < n; i ++) {
        if (mn == p[i]) ans[i] = 1;
    }
    return ans;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    for (int I = 0; I < T; I ++){
        int n, m;
        cin >> n >> m;
        vector<int> r(n), 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 (int i = 0; i < ans.size(); ++i) cout << ans[i] << ' ';
    }
}
/*
3
10 15 13
2
0 2 20
0 2 -11
*/

Compilation message (stderr)

keys.cpp: In function 'int main()':
keys.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i = 0; i < ans.size(); ++i) cout << ans[i] << ' ';
      |                         ~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccfjvMGh.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccppCZjh.o:keys.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status