Submission #605665

#	Time	Username	Problem	Language	Result	Execution time	Memory
605665		keta_tsimakuridze	Keys (IOI21_keys)	C++17	100 / 100	1103 ms	59768 KiB

keys

#include <vector>
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 3e5 + 5;
int bad[N], p[N], f[N], vis[N], x[N];
vector<int> need[N];
pair<int, vector<int> > ans;
vector<pair<int,int > > V[N];
void upd(pair<int, vector<int> > &ans, vector<int> x) {
    if(ans.f > x.size()) {
        ans = {x.size(), x};
        return;
    } else if(ans.f == x.size()) {
        while(x.size()) ans.s.push_back(x.back()), x.pop_back();
    }
}
int dfs(int u) {

    if(f[u]) return p[u];
    f[u] = 1;
    return p[u] = dfs(x[u]);
}
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(), m = u.size();
    for(int i = 0; i < m; i++) V[u[i]].push_back({v[i], c[i]}), V[v[i]].push_back({u[i], c[i]});
    for(int i = 0; i < n; i++) p[i] = i, bad[i] = 0, f[i] = 0;
    ans.f = n;
    for(int X = 1; X <= n; X++) {
        int FF = 0;
        for(int i = 0; i < n; i++) {
            x[i] = p[i];
            if(bad[i]) continue;
            if(p[i] == i) {
                queue<int> q;
                vector<int> remk, remv;
                q.push(i); remv.push_back(i);
                int F = 0;
                while(q.size()) {
                    int u = q.front();
                    vis[u] = 1;
                    int k = r[u]; //cout << "++" << u << " " << k << " " << f[1] << endl;
                    if(!f[k]) {
                        for(int i = 0; i < need[k].size(); i++) {
                            int v = need[k][i];
                            if(vis[v]) continue;
                            if(p[u] != p[v]) {
                                // p[u] --> p[v]
                                F = 1; FF |= 1;
                                x[p[u]] = p[v];
                                break;
                            }
                            else q.push(v), vis[v] = 1, remv.push_back(v);
                        }
                        if(F) break;
                        f[k] = 1;
                        remk.push_back(k);

                    }
                    q.pop();
                    for(int i = 0; i < V[u].size(); i++) {
                        int v = V[u][i].f, k = V[u][i].s;
                        if(vis[v]) continue;
                        if(!f[k]) need[k].push_back(v), remk.push_back(k);
                        else if(p[u] != p[v]) {
                            // p[u] --> p[v]
                            F = 1; FF |= 1;
                            x[p[u]] = p[v];
                            break;
                        }
                        else q.push(v), vis[v] = 1, remv.push_back(v);
                    }
                    if(F) break;
                }
                if(!F) upd(ans, remv), bad[i] = 1;
                for(int i = 0; i < remk.size(); i++) need[remk[i]].clear(), f[remk[i]] = 0;
                for(int i = 0; i < remv.size(); i++) vis[remv[i]] = 0;
            }
        }
            if(!FF) break;
            for(int i = 0; i < n; i++) {
                f[i] = 0;
            }
            for(int i = 0; i < n; i++) {
                if(bad[i]) continue;
                p[i] = dfs(i);
            }
            for(int i = 0; i < n; i++) f[i] = 0;

    }
    vector<int> Ans(n);
    for(int i = 0; i < ans.s.size(); i++) Ans[ans.s[i]] = 1;
    return Ans;
}

Compilation message (stderr)

keys.cpp: In function 'void upd(std::pair<int, std::vector<int> >&, std::vector<int>)':
keys.cpp:12:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if(ans.f > x.size()) {
      |        ~~~~~~^~~~~~~~~~
keys.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     } else if(ans.f == x.size()) {
      |               ~~~~~~^~~~~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:45:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                         for(int i = 0; i < need[k].size(); i++) {
      |                                        ~~^~~~~~~~~~~~~~~~
keys.cpp:62:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                     for(int i = 0; i < V[u].size(); i++) {
      |                                    ~~^~~~~~~~~~~~~
keys.cpp:77:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                 for(int i = 0; i < remk.size(); i++) need[remk[i]].clear(), f[remk[i]] = 0;
      |                                ~~^~~~~~~~~~~~~
keys.cpp:78:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 for(int i = 0; i < remv.size(); i++) vis[remv[i]] = 0;
      |                                ~~^~~~~~~~~~~~~
keys.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i = 0; i < ans.s.size(); i++) Ans[ans.s[i]] = 1;
      |                    ~~^~~~~~~~~~~~~~

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