제출 #802681

#제출 시각아이디문제언어결과실행 시간메모리
802681SamAnd열쇠 (IOI21_keys)C++17
37 / 100
82 ms20300 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define m_p make_pair #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() const int N = 2003; int n; vector<pair<int, int> > g[N]; bool c[N]; bool cc[N]; vector<int> v[N]; int stup(int x, const vector<int>& r) { memset(c, false, sizeof c); memset(cc, false, sizeof cc); for (int i = 0; i < n; ++i) v[i].clear(); queue<int> q; q.push(x); while (!q.empty()) { int x = q.front(); q.pop(); if (c[x]) continue; c[x] = true; cc[r[x]] = true; while (!v[r[x]].empty()) { q.push(v[r[x]].back()); v[r[x]].pop_back(); } for (int i = 0; i < sz(g[x]); ++i) { int h = g[x][i].fi; if (cc[g[x][i].se]) q.push(h); else v[g[x][i].se].push_back(h); } } int ans = 0; for (int i = 0; i < n; ++i) ans += c[i]; return ans; } std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { n = sz(r); int m = sz(u); std::vector<int> ans(n, 0); for (int i = 0; i < m; ++i) { g[u[i]].push_back(m_p(v[i], c[i])); g[v[i]].push_back(m_p(u[i], c[i])); } vector<int> s; for (int i = 0; i < n; ++i) s.push_back(stup(i, r)); int minu = s[0]; for (int i = 0; i < n; ++i) { minu = min(minu, s[i]); } for (int i = 0; i < n; ++i) { if (s[i] == minu) 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...