Submission #1195629

#TimeUsernameProblemLanguageResultExecution timeMemory
1195629AmrKeys (IOI21_keys)C++20
9 / 100
3098 ms105404 KiB
#include <vector> #include<bits/stdc++.h> using namespace std; typedef long long ll; #define F first #define S second #define sz size() const int N = 3e5+7; vector<vector<ll> > e; ll p[N], siz[N]; set<ll> in[N], out[N], s[N]; ll n, m; ll get(ll x) { if(x==p[x]) return x; return p[x] = get(p[x]); } void merg(ll a, ll b) { while(in[a].sz) { auto it = in[a].begin(); in[b].insert(*it); out[*it].insert(b); out[*it].erase(a); in[a].erase(it); } while(out[a].sz) { auto it = out[a].begin(); out[b].insert(*it); in[*it].insert(b); in[*it].erase(a); out[a].erase(it); } for(auto it : s[a]) s[b].insert(it); siz[b] += siz[a]; p[a] = b; } bool cmp(vector<ll> v1, vector<ll> v2) { return v1[2] < v2[2]; } std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { // std::vector<int> ans(r.size(), 1); n = r.sz, m = u.sz; for(int i = 0; i < m; i++) { e.push_back({u[i],v[i],c[i]}); e.push_back({v[i],u[i],c[i]}); } sort(e.begin(),e.begin()+2*m,cmp); for(int i = 0; i < n; i++) { p[i] = i; s[i].insert(r[i]); siz[i] = 1; } for(int i = 0; i < 2*m; i++) { ll a = e[i][0], b = e[i][1], w = e[i][2]; // cout << a << " " << b << " " << w << " " << get(a) << endl; a = get(a), b = get(b); if(a==b) continue; if(s[a].find(w)==s[a].end()) continue; if(in[a].find(b)==in[a].end()) { out[a].insert(b); in[b].insert(a); } else { in[a].erase(b); out[b].erase(a); merg(a,b); } } ll mn = 1e9; for(int i = 0; i < n; i++) { ll x = get(i); if(out[x].sz==0) { mn = min(mn,siz[x]); } // cout << x << " " << siz[x] << " " << out[x].sz << endl; } vector<int> ans(n,0); for(int i = 0; i < n; i++) { ll x = get(i); if(out[x].sz==0&&siz[x]==mn) { ans[i] = 1; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...