# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
441877 | Stickfish | Keys (IOI21_keys) | C++17 | 3070 ms | 30088 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
const int MAXN = 3e5 + 123;
vector<pair<int, int>> edg[MAXN];
int keyget[MAXN];
bitset<MAXN> used;
vector<int> solve_quad(int n){
vector<int> ans(n);
bitset<MAXN> used_cl;
vector<vector<int>> reachable(n);
for(int i = 0; i < n; ++i){
used.reset();
used_cl.reset();
for(int j = 0; j < n; ++j){
reachable[j].clear();
}
vector<int> stck = {i};
while(stck.size()){
int v = stck.back();
stck.pop_back();
if(used[v])
continue;
used[v] = used_cl[keyget[v]] = 1;
for(auto u : reachable[keyget[v]]){
stck.push_back(u);
}
reachable[keyget[v]].clear();
for(auto [u, keyneed] : edg[v]){
if(used[u])
continue;
if(used_cl[keyneed]){
stck.push_back(u);
} else {
reachable[keyneed].push_back(u);
}
}
}
//for(int j = 0; j < n; ++j)
//cout << used[j];
//cout << '\n';
ans[i] = used.count();
}
return ans;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
int m = u.size();
for(int i = 0; i < n; ++i){
keyget[i] = r[i];
}
for(int i = 0; i < m; ++i){
edg[u[i]].push_back({v[i], c[i]});
edg[v[i]].push_back({u[i], c[i]});
}
if(n <= 2000 && m <= 2000){
vector<int> ans = solve_quad(n);
int mn = *min_element(ans.begin(), ans.end());
for(int i = 0; i < n; ++i)
ans[i] = (ans[i] == mn);
return ans;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |