#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct edge {
int x, y, id;
};
bool cmp(edge e1, edge e2) {
if (e1.x == e2.x) {
return e1.y > e2.y;
} else {
return e1.x < e2.x;
}
}
vector<vector<int>>g, gp;
vector<bool>visited;
vector<int>order;
void dfs1(int node){
visited[node] = true;
for (int to : g[node]) {
if (!visited[to]) {
dfs1(to);
}
}
order.eb(node);
}
void dfs2(int node) {
visited[node] = true;
for (int to : gp[node]) {
if (!visited[to]) {
dfs2(to);
}
}
}
void solve() {
int a, b, m;
cin >> a >> b >> m;
vector<edge>E(m);
for (int i = 0; i < m; ++i) {
cin >> E[i].x >> E[i].y;
E[i].id = i;
}
sort(all(E), cmp);
g.resize(a + b + 1);
gp.resize(a + b + 1);
for (int i = 1; i < a; ++i) {
g[i].eb(i + 1);
}
for (int i = a + 1; i < a + b; ++i) {
g[i].eb(i + 1);
}
int maxY = 0;
vector<char>res(m);
for (edge e : E) {
if (e.y <= maxY) {
res[e.id] = '0';
g[e.x].eb(a + e.y);
} else {
res[e.id] = '1';
g[a + e.y].eb(e.x);
maxY = e.y;
}
}
for (int i = 1; i <= a + b; ++i) {
for (int to : g[i]) {
gp[to].eb(i);
}
}
visited.assign(a + b + 1, false);
for (int i = 1; i <= a + b; ++i) {
if (!visited[i]) {
dfs1(i);
}
}
reverse(all(order));
visited.assign(a + b + 1, false);
int compos = 0;
for (int i : order) {
if (!visited[i]) {
dfs2(i);
++compos;
}
}
cout << compos << ln;
for (char c : res) {
cout << c << ' ';
}
cout << ln;
}
int main() {
ios_base::sync_with_stdio(false);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
