| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 511799 | betterdanjoe | Keys (IOI21_keys) | C++17 | 0 ms | 0 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 <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define ff first
#define ss second
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
const ll llinf = 1e18;
const int mod = 1e9 + 7;
const double PI = acos(-1);
struct chash {
const uint64_t C = ll(2e18*PI)+71;
const int RANDOM = rand();
ll operator()(ll x) const {
return __builtin_bswap64((x^RANDOM)*C);
}
};
template<class K> using sset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
template<class K, class V> using gphash = gp_hash_table<K, V, chash, equal_to<K>, direct_mask_range_hashing<>, linear_probe_fn<>, hash_standard_resize_policy< hash_exponential_size_policy<>, hash_load_check_resize_trigger<>, true> >;
inline ll ceil0(ll a, ll b) {
return a / b + ((a ^ b) > 0 && a % b);
}
inline ll floor0(ll a, ll b) {
return a / b - ((a ^ b) < 0 && a % b);
}
void setIO() {
ios_base::sync_with_stdio(0); cin.tie(0);
}
void dfs(int x);
set<pii> g[400000];
set<int> comp[400000];
vector<pii> edge[400000];
stack<int> s;
bool in[400000];
int arr[400000], par[400000];
int low[400000], d[400000], t = 1;
int sz[400000];
vector<int> vis;
int find(int x){
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int a, int b){
assert(a != b);
if(comp[a].size() < comp[b].size()) comp[a].swap(comp[b]);
if(g[a].size() < g[b].size()) g[a].swap(g[b]);
for(int i : comp[b]) comp[a].insert(i);
for(pii i : g[b]) g[a].insert(i);
g[b].clear();
comp[b].clear();
par[b] = a;
}
vector<int> comb[400000];
void dfs(int x){
low[x] = d[x] = t++;
s.push(x);
in[x] = true;
cout << find(x) << " " << x << endl;
vector<pii> rem;
for(pii i : g[x]) if(find(i.ff) != i.ff) rem.pb(i);
for(pii i : rem) g[x].erase(i), g[x].insert({find(i.ff), i.ss});
for(pii i : g[x]){
if(comp[x].find(i.ss) == comp[x].end()) continue;
if(!d[i.ff]){
dfs(i.ff);
low[x] = min(low[x], low[i.ff]);
} else if(in[i.ff]) low[x] = min(low[x], d[i.ff]);
}
if(low[x] == d[x]){
while(s.top() != x){
in[s.top()] = false;
comb[x].pb(s.top());
s.pop();
}
vis.pb(x);
in[x] = false;
s.pop();
}
}
int main(){
setIO();
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> arr[i];
for(int i = 0; i < n; i++) par[i] = i;
for(int i = 0; i < n; i++) comp[i].insert(arr[i]);
vector<pair<pii, int>> v;
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
v.pb({{a, b}, c});
g[a].insert({b, c});
g[b].insert({a, c});
}
vector<int> nxt;
for(int i = 0; i < n; i++) nxt.pb(i);
while(nxt.size()){
vis.clear();
for(int i : nxt) if(!d[i]) dfs(i);
nxt.clear();
for(int i : vis){
if(comb[i].size()) nxt.pb(i);
d[i] = 0;
for(int j : comb[i]){
merge(i, j);
}
comb[i].clear();
}
t = 1;
for(int i = 0; i < n; i++) cout << find(i) << " ";
cout << endl;
}
for(int i = 0; i < n; i++) sz[find(i)]++;
bool fail[n];
memset(fail, false, sizeof(fail));
for(auto i : v){
int a = find(i.ff.ff);
int b = find(i.ff.ss);
if(a == b) continue;
if(comp[a].find(i.ss) == comp[a].end() ^ comp[b].find(i.ss) == comp[b].end()){
if(comp[a].find(i.ss) == comp[a].end()) fail[b] = true;
else fail[a] = true;
}
}
int mn = inf;
for(int i = 0; i < n; i++) if(!fail[find(i)]) mn = min(mn, sz[find(i)]);
for(int i = 0; i < n; i++) if(sz[find(i)] > mn) fail[find(i)] = true;
for(int i = 0; i < n; i++){
if(i) cout << " ";
cout << !fail[find(i)];
}
}