Submission #605648

#	Time	Username	Problem	Language	Result	Execution time	Memory
605648		keta_tsimakuridze	Keys (IOI21_keys)	C++17	0 / 100	3063 ms	9712 KiB

keys

#include <vector>
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 2e5 + 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;
    while(true) {
        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);
                int F = 0;
                while(q.size()) {
                    int u = q.front();
                    vis[u] = 1; remv.push_back(u);
                    int k = r[u]; //cout << "++" << u << " " << k << " " << f[1] << endl;
                    if(!f[k]) {
                        for(int i = 0; i < need[k].size(); i++) {
                            q.push(need[k][i]);
                        }
                        f[k] = 1;
                        remk.push_back(k);
                    }
                    q.pop(); vis[u] = 1;
                    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);
                        else if(p[u] != p[v]) {
                            // p[u] --> p[v]
                            F = 1; FF |= 1;
                            x[p[u]] = p[v];
                         //   cout << p[u] << "-->" << p[v] << endl;
                            break;
                        }
                        else q.push(v), vis[v] = 1;
                    }
                    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(p[i] == i) p[i] = dfs(i);
              //  cout << p[i] << " ";
            } //cout << endl;
            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:52: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]
   52 |                     for(int i = 0; i < V[u].size(); i++) {
      |                                    ~~^~~~~~~~~~~~~
keys.cpp:68:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 for(int i = 0; i < remk.size(); i++) need[remk[i]].clear(), f[remk[i]] = 0;
      |                                ~~^~~~~~~~~~~~~
keys.cpp:69:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 for(int i = 0; i < remv.size(); i++) vis[remv[i]] = 0;
      |                                ~~^~~~~~~~~~~~~
keys.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 0; i < ans.s.size(); i++) Ans[ans.s[i]] = 1;
      |                    ~~^~~~~~~~~~~~~~

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