제출 #1215506

#제출 시각아이디문제언어결과실행 시간메모리
1215506dostsKeys (IOI21_keys)C++20
20 / 100
3098 ms412056 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 3e5+1, inf = 2e9; vi edges[LIM],egdes[LIM], vis(LIM,0), col(LIM); vi order; void topo(int node) { if (vis[node]) return; vis[node] = 1; for (auto it : edges[node]) { topo(it); } order.push_back(node); } int color(int node,int c) { if (vis[node]) return 0; vis[node] = 1; col[node] = c; int ans = 1; for (auto it : egdes[node]) ans+=color(it,c); return ans; } 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(),m = u.size(); vi canreach[n]; set<int> cols[n]; vector<pii> edg[n]; for (int i = 0;i<m;i++) { if (r[u[i]] == c[i]) canreach[v[i]].push_back(u[i]); if (r[v[i]] == c[i]) canreach[u[i]].push_back(v[i]); edg[u[i]].push_back({v[i],c[i]}); edg[v[i]].push_back({u[i],c[i]}); } queue<pii> q; for (int i = 0;i<n;i++) q.push({i,r[i]}),cols[i].insert(r[i]); while (!q.empty()) { pii f = q.front(); q.pop(); int city = f.ff,col = f.ss; for (auto it : canreach[city]) { if (!cols[it].count(col)) { cols[it].insert(col); q.push({it,col}); } } for (auto it : edg[city]) { if (it.ss == col) { canreach[it.ff].push_back(city); for (auto it : cols[it.ff]) { if (!cols[city].count(it)) { cols[city].insert(it); q.push({city,it}); } } } } } for (int i = 0;i<n;i++) { for (auto it : edg[i]) { if (cols[i].count(it.ss)) { edges[i].push_back(it.ff); egdes[it.ff].push_back(i); } } } vi ans(n,0); int fnd = 0; for (int i = 0;i<n;i++) { if (edges[i].empty()) { fnd = 1; ans[i] = 1; } } if (fnd) return ans; for (int i = 0;i<n;i++) topo(i); reverse(all(order)); vis.assign(n,0); int cc = 0; vi szs; for (int i = 0;i<n;i++) { if (!vis[order[i]]) { szs.push_back(color(order[i],cc++)); } } reverse(all(order)); for (auto i : order) { for (auto it : edges[i]) { if (col[i] != col[it]) { szs[col[i]]+=szs[col[it]]; } } } int x = inf; for (int i=0;i<n;i++) { if (szs[col[i]] < x) { x = szs[col[i]]; } } for (int i = 0;i<n;i++) { if (szs[col[i]] == x) 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...