Submission #751706

#	Time	Username	Problem	Language	Result	Execution time	Memory
751706		Ronin13	열쇠 (IOI21_keys)	C++17	37 / 100	3084 ms	23816 KiB

keys

#include <vector>
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;


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();
	vector <vector <pii> > g(n + 1);
	for(int i = 0; i < u.size(); ++i){
        g[u[i]].pb({v[i], c[i]});
        g[v[i]].pb({u[i], c[i]});
	}
	vector <int> ans(n);
	int mn = 1e9;
	vector <int> aa(n);
    for(int s = 0; s < n; s++){
        vector <bool> active(n);
        vector <bool> used(n);
        queue <int> q;
        vector <vector <int> > cl(n);
        q.push(s);
        used[s] = true;
        int cnt = 0;
        while(!q.empty()){
            cnt++;
            int v = q.front();
            if(!active[r[v]]){
                for(int to : cl[r[v]]){
                    if(used[to]) continue;
                    used[to] = true, q.push(to);
                }
            }
            active[r[v]] = true;
            q.pop();
            for(auto x : g[v]){
                if(used[x.f]) continue;
                if(!active[x.s]){
                    cl[x.s].pb(x.f);
                    continue;
                }
                q.push(x.f);
                used[x.f] = true;
            }
        }
        mn = min(mn, cnt);
        aa[s] = cnt;
    }
    for(int i = 0; i < n; i++)
        ans[i] = (aa[i] == mn);
	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:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i = 0; i < u.size(); ++i){
      |                 ~~^~~~~~~~~~
keys.cpp:56:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   56 |     for(int i = 0; i < n; i++)
      |     ^~~
keys.cpp:58:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |  return ans;
      |  ^~~~~~

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