#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 400'010;
vector<int> g[MAXN];
vector<int> g_rev[MAXN];
bool cmp(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
if(a.first.first==b.first.first)return a.first.second > b.first.second;
return a.first.first < b.first.first;
}
vector<int> topo;
vector<bool> used(MAXN);
void dfs(int v) {
used[v] = true;
for(int i:g[v])
if(!used[i])
dfs(i);
topo.push_back(v);
}
int cnt;
void dfs2(int v) {
used[v] = true;
cnt++;
for(int i:g_rev[v])
if(!used[i])
dfs2(i);
}
int32_t main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
int a, b;
cin >> a >> b;
int m;
cin >> m;
for(int i = 1;i<a;i++) {
g[i].push_back(i+1);
g_rev[i+1].push_back(i);
}
for(int i = 1;i<b;i++) {
g[i+a].push_back(i+1+a);
g_rev[i+a+1].push_back(i+a);
}
vector<pair<pair<int,int>,int>> v(m);
for(int i = 0;i<m;i++){
cin>>v[i].first.first>>v[i].first.second;
v[i].second=i;
}
sort(v.begin(), v.end(), cmp);
int MAXY = 0;
bool ans[m];
for(int i = 0;i<m;i++) {
if(v[i].first.second > MAXY) {
g[v[i].first.second+a].push_back(v[i].first.first);
g_rev[v[i].first.first].push_back(v[i].first.second+a);
ans[v[i].second] = 1;
MAXY=v[i].first.second;
}
else {
g[v[i].first.first].push_back(v[i].first.second+a);
g_rev[v[i].first.second+a].push_back(v[i].first.first);
ans[v[i].second] = 0;
}
}
for(int i = 1;i<=a;i++) {
if(!used[i])
dfs(i);
}
for(int i = 1;i<=b;i++) {
if(!used[i+a])
dfs(i+a);
}
reverse(topo.begin(), topo.end());
used.assign(MAXN, 0);
long long res=0;
for(int i:topo) {
cnt = 0;
if(!used[i]) {
dfs2(i);
res++;
}
}
cout << res << "\n";
for(int i = 0;i<m;i++){
cout<<ans[i]<<" ";
}
cout << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
