Submission #491490

#	Time	Username	Problem	Language	Result	Execution time	Memory
491490		doowey	Keys (IOI21_keys)	C++17	67 / 100	3093 ms	61356 KiB

keys

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = (int)3e5 + 1;
vector<pii> T[N];
int col[N];
int low = (int)1e9;
vector<int> lis;
bool mark[N];

void shuffle(vector<int> &shf){
    int ii, jj;
    int m = shf.size();
    for(int i = 0 ; i < shf.size(); i ++ ){
        ii = ((int)rng() % m + m) % m;
        jj = ((int)rng() % m + m) % m;
        swap(shf[ii], shf[jj]);
    }
}

bool vis[N];
vector<int> nw[N];
bool reg_col[N];

void bfs(int node){
    mark[node]=true;
    queue<int> que;
    que.push(node);
    vector<int> colors;
    vector<int> nodes;
    colors.push_back(col[node]);
    nodes.push_back(node);
    vis[node]=true;

    bool endet = false;

    while(!que.empty() && endet == false){
        node = que.front();
        if(!reg_col[col[node]]){
            for(auto x : nw[col[node]]){
                if(!vis[x]){
                    vis[x]=true;
                    nodes.push_back(x);
                    que.push(x);
                    if(mark[x]){
                        endet=true;
                        break;
                    }
                }
            }
        }
        if(endet) break;
        reg_col[col[node]]=true;
        que.pop();
        for(auto x : T[node]){
            if(vis[x.fi]) continue;
            colors.push_back(x.se);

            if(reg_col[x.se]){

                nodes.push_back(x.fi);
                vis[x.fi] = true;
                que.push(x.fi);
                if(mark[x.fi]){
                    endet = true;
                    break;
                }
            }
            else{
                nw[x.se].push_back(x.fi);
            }
        }
    }
    for(auto x : colors){
        nw[x].clear();
    }
    for(auto x : nodes){
        reg_col[col[x]]=false;
        vis[x] = false;
    }
    if(endet){
        return;
    }
    if(nodes.size() < low){
        low = nodes.size();
        lis.clear();
    }
    if(nodes.size() == low){
        for(auto x : nodes){
            lis.push_back(x);
        }
    }
}

vector<int> ans;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {

    int n = r.size();
    ans.resize(n, 0);
    for(int i = 0 ; i < n; i ++ ){
        col[i] = r[i];
    }
    for(int i = 0 ; i < u.size(); i ++ ){
        T[u[i]].push_back(mp(v[i], c[i]));
        T[v[i]].push_back(mp(u[i], c[i]));
    }
    vector<int> ord;
    for(int i = 0 ;i  < n; i ++ ){
        ord.push_back(i);
    }
    shuffle(ord);
    for(auto x : ord){
        bfs(x);
    }
    for(auto q : lis){
        ans[q]=1;
    }
	return ans;

}

Compilation message (stderr)

keys.cpp: In function 'void shuffle(std::vector<int>&)':
keys.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0 ; i < shf.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
keys.cpp: In function 'void bfs(int)':
keys.cpp:94:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     if(nodes.size() < low){
      |        ~~~~~~~~~~~~~^~~~~
keys.cpp:98:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |     if(nodes.size() == low){
      |        ~~~~~~~~~~~~~^~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i = 0 ; i < u.size(); i ++ ){
      |                     ~~^~~~~~~~~~

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