Submission #600477

#	Time	Username	Problem	Language	Result	Execution time	Memory
600477		2fat2code	Keys (IOI21_keys)	C++17	67 / 100	3096 ms	58776 KiB

keys

#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 300005;

int n, m, par[nmax], kek[nmax];
bitset<nmax>viz, keys, lol;
vector<pair<int,int>>nod[nmax];
vector<int>waiting[nmax];
vector<pair<int,int>>change;
vector<int>lmao;

int findpar(int x){
    if(par[x] != x){
        par[x] = findpar(par[x]);
    }
    return par[x];
}

void bfs(int s, vector<int>&type){
    keys.reset();
    viz.reset();
    queue<int>q;
    q.push(s);
    lmao.push_back(s);
    viz[s] = 1;
    vector<int>zb;
    while(q.size()){
        auto it = q.front();
        keys[type[it-1]] = 1;
        q.pop();
        for(auto it1 : waiting[type[it-1]]){
            if(findpar(it1) != s){
                change.push_back({s, par[it1]});
                goto next;
            }
            if(!viz[it1]){
                q.push(it1);
                lmao.push_back(it1);
                viz[it1] = 1;
            }
        }
        waiting[type[it-1]].clear();
        for(auto it1 : nod[it]){
            if(findpar(it1.fr) != s && keys[it1.sc]){
                change.push_back({s, par[it1.fr]});
                goto next;
            }
            if(keys[it1.sc] && !viz[it1.fr]){
                q.push(it1.fr);
                viz[it1.fr] = 1;
                lmao.push_back(it1.fr);
            }
            else if(!keys[it1.sc]){
                waiting[it1.sc].push_back(it1.fr);
                zb.push_back(it1.sc);
            }
        }
    }
    next:;
    for(auto it : zb) waiting[it].clear();
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n = r.size();
    vector<int>ans(n);
    m = u.size();
    for(int i=0;i<m;i++){
        nod[u[i]+1].push_back({v[i]+1, c[i]});
        nod[v[i]+1].push_back({u[i]+1, c[i]});
    }
    for(int i=1;i<=n;i++) par[i] = i;
    while(true){
        lol.reset();
        change.clear();
        vector<int>roots;
        for(int i=1;i<=n;i++){
            if(par[i] == i){
                roots.push_back(i);
            }
        }
        for(auto it : roots){
            bfs(it, r);
        }
        if(!change.size()) break;
        else{
            for(auto it : change){
                if(!lol[it.fr]){
                    par[it.fr] = it.sc;
                    lol[it.sc] = 1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(par[i] == i){
            lmao.clear();
            bfs(i, r);
            int xd = lmao.size();
            for(auto it : lmao){
                kek[it] = xd;
            }
        }
    }
    int maxi = 1e18;
    for(int i=1;i<=n;i++){
        if(kek[i] && maxi > kek[i]) maxi = kek[i];
    }
    for(int i=1;i<=n;i++){
        if(maxi == kek[i]) ans[i - 1] = 1;
    }
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:111:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
  111 |     int maxi = 1e18;
      |                ^~~~

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