Submission #1215460

#TimeUsernameProblemLanguageResultExecution timeMemory
1215460thelegendary08Keys (IOI21_keys)C++17
0 / 100
0 ms324 KiB
#include "keys.h" #include<bits/stdc++.h> #define vi vector<int> #define f0r(i,n) for(int i = 0; i<n; i++) #define mp make_pair #define pb push_back #define FOR(i, k, n) for(int i = k; i<n; i++) #define pii pair<int,int> #define dout(x) cout<<x<<' '<<#x<<'\n'; #define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n'; #define vvi vector<vi> #define vb vector<bool> 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(); int m = u.size(); vi ans(n); vvi adj(n); vvi edgcol(n); vvi edgnode(n); f0r(i,m){ adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]); edgcol[c[i]].pb(i); edgnode[u[i]].pb(i); edgnode[v[i]].pb(i); } vi req(m); vi cnts; f0r(i,n){ queue<int>q; q.push(i); vb vis(n); vis[i] = 1; for(auto x : edgnode[i]){ req[x]++; } set<int>col; while(!q.empty()){ int node = q.front(); q.pop(); if(!col.count(r[node])){ col.insert(r[node]); for(auto x : edgcol[r[node]]){ req[x]++; if(req[x] == 2){ if(!vis[u[x]])q.push(u[x]); if(!vis[v[x]])q.push(v[x]); } } } for(auto nxt : adj[node]){ if(vis[nxt])continue; vis[nxt] = 1; for(auto x : edgnode[nxt]){ if(!vis[u[x]] || !vis[v[x]]){ req[x]++; if(req[x] == 2){ if(!vis[u[x]])q.push(u[x]); if(!vis[v[x]])q.push(v[x]); } } } } } int cnt = 0; f0r(i,n){ if(vis[i])cnt++; } cnts.pb(cnt); } int mn = *min_element(cnts.begin(), cnts.end()); f0r(i,n){ if(cnts[i] == 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...