Submission #788391

#	Time	Username	Problem	Language	Result	Execution time	Memory
788391		alexander707070	열쇠 (IOI21_keys)	C++17	37 / 100	3069 ms	10860 KiB

keys

#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

int n,m,cnt;
bool used[MAXN],reach[MAXN],dali;
int ans[MAXN],mins;
vector<int> sol,perm,edges;

vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
    n=int(r.size()); m=int(u.size());
    mins=n;

    for(int i=0;i<n;i++)perm.push_back(i);
    random_shuffle(perm.begin(),perm.end());

    for(int i:perm){
        for(int f=0;f<n;f++){
            used[f]=false; reach[f]=false;
        }

        edges.clear();
        for(int f=0;f<m;f++)edges.push_back(f);

        used[r[i]]=true; reach[i]=true;
        dali=true; cnt=1;

        while(dali){
            dali=false;
            for(int k=0;k<edges.size();k++){

                if(reach[u[edges[k]]] and !reach[v[edges[k]]] and used[c[edges[k]]]){
                    reach[v[edges[k]]]=true; used[r[v[edges[k]]]]=true;
                    dali=true; cnt++;

                    swap(edges[k],edges[edges.size()-1]); edges.pop_back();
                }

                if(!reach[u[edges[k]]] and reach[v[edges[k]]] and used[c[edges[k]]]){
                    reach[u[edges[k]]]=true; used[r[u[edges[k]]]]=true;
                    dali=true; cnt++;

                    swap(edges[k],edges[edges.size()-1]); edges.pop_back();
                }
            }
            if(cnt>mins)break;
        }

        ans[i]=cnt;
        mins=min(mins,cnt);
    }

    for(int i=0;i<n;i++){
        if(ans[i]==mins){
            sol.push_back(1);
        }else sol.push_back(0);
    }

    return sol;
}

/*
int main(){
    find_reachable({0, 1, 1, 2},{0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
}
*/

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:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for(int k=0;k<edges.size();k++){
      |                         ~^~~~~~~~~~~~~

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