Submission #570897

#	Time	Username	Problem	Language	Result	Execution time	Memory
570897		doowey	Keys (IOI21_keys)	C++17	37 / 100	3066 ms	39616 KiB

keys

#include "keys.h"
#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


const int N = (int)3e5 + 1;

vector<pii> T[N];
int col[N];
bool collect[N];
vector<int> st[N];
bool vis[N];

vector<int> nds;
vector<int> keys;

void clean(){
    for(auto x : nds){
        vis[x] = false;
    }
    for(auto x : keys){
        collect[x] = false;
        st[x].clear();
    }
    nds.clear();
    keys.clear();
}

void travel(int node){
    queue<int> que;
    que.push(node);
    vis[node]=true;
    int cur;

    while(!que.empty()){
        cur = que.front();
        que.pop();
        collect[col[cur]] = true;
        keys.push_back(col[cur]);
        nds.push_back(cur);
        for(auto x : T[cur]){
            if(vis[x.fi]) continue;
            keys.push_back(x.se);
            if(collect[x.se]){
                vis[x.fi]=true;
                que.push(x.fi);
            }
            else{
                st[x.se].push_back(x.fi);
            }
        }
        for(auto x : st[col[cur]]){
            if(vis[x]) continue;
            vis[x] = true;
            que.push(x);
        }
        st[col[cur]].clear();
    }
}


vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int m = u.size();
    int n = r.size();
    for(int i = 0 ; i < n; i ++ ){
        col[i] = r[i];
    }
    for(int i = 0 ; i < m ; i ++ ){
        T[u[i]].push_back(mp(v[i], c[i]));
        T[v[i]].push_back(mp(u[i], c[i]));
    }
    vector<int> sol(n);
    int vis = n + 1;
    vector<int> qq;
    for(int i = 0 ; i < n; i ++ ){
        travel(i);
        if(nds.size() < vis){
            vis = nds.size();
            qq = {i};
        }
        else if(nds.size() == vis){
            qq.push_back(i);
        }
        clean();
    }
    for(auto x : qq){
        sol[x] = 1;
    }
    return sol;
}

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:85:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |         if(nds.size() < vis){
      |            ~~~~~~~~~~~^~~~~
keys.cpp:89:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         else if(nds.size() == vis){
      |                 ~~~~~~~~~~~^~~~~~

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