Submission #1243547

#TimeUsernameProblemLanguageResultExecution timeMemory
1243547gaga999Usmjeravanje (COCI22_usmjeravanje)C++20
0 / 110
5 ms9796 KiB
#include <bits/stdc++.h> using namespace std; #define pb emplace_back #define iter(x) (x).begin(), (x).end() #define size(x) (int)(x).size() #define INF 0x3f3f3f3f #define lowbit(x) ((x) & -(x)) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) typedef long long ll; typedef pair<int, int> pii; void db() { cerr << endl; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } const int N = 4e5 + 5; int dfn[N], low[N], ar[N], br[N], ctd, sum; bool ans[N]; vector<int> sk, eg[N]; void dfs(int u) { dfn[u] = low[u] = ++ctd; sk.pb(u); for (int v : eg[u]) { if (!dfn[v]) { dfs(v); tmin(low[u], low[v]); } else if (dfn[v] < dfn[u]) { tmin(low[u], dfn[v]); } } if (dfn[u] == low[u]) { int v; do { v = sk.back(); sk.pop_back(); } while (v != u); sum++; } dfn[u] = INF; } signed main() { cin.tie(0)->sync_with_stdio(0); int a, b, m; cin >> a >> b >> m; for (int i = 0; i < m; i++) cin >> ar[i] >> br[i]; vector<int> od(m); iota(iter(od), 0); sort(iter(od), [](int x, int y) { return ar[x] < ar[y] || (ar[x] == ar[y] && br[x] > br[y]); }); for (int i = 2; i <= a; i++) eg[i - 1].pb(i); for (int i = 2 + a; i <= a + b; i++) eg[i - 1].pb(i); int mx = 0; for (int i : od) { if (br[i] > mx) ans[i] = 1, eg[br[i] + a].pb(ar[i]), mx = br[i]; else eg[ar[i]].pb(br[i] + a); } for (int i = 1; i <= a + b; i++) if (!dfn[i]) dfs(i); cout << sum << '\n'; for (int i = 0; i < m; i++) cout << ans[i] << " \n"[i == m - 1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...