#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const int MAX_N = 5e5 + 10;
bool in[MAX_N], used[MAX_N];
vector<pair<int, int> > g[MAX_N];
int finalColours[MAX_N];
int l, r, m;
bool gotThrough[MAX_N];
void dfs(int x, bool flag) {
gotThrough[x] = true;
for(auto it : g[x]) {
if(!used[it.second]) {
used[it.second] = true;
in[it.second] = flag;
dfs(it.first, flag ^ 1);
}
}
}
int solve(vector<pair<pair<int, int>, int> > &edges) {
cout << edges.size() << endl;
vector<int> active;
for(auto it : edges) {
g[it.first.first].resize(0);
g[it.first.second].resize(0);
}
for(auto it : edges) {
active.push_back(it.first.first);
active.push_back(it.first.second);
used[it.second] = false;
g[it.first.first].push_back({it.first.second, it.second});
gotThrough[it.first.first] = false;
gotThrough[it.first.second] = false;
g[it.first.second].push_back({it.first.first, it.second});
}
sort(active.begin(), active.end());
active.resize(unique(active.begin(), active.end()) - active.begin());
bool allOne = true;
for(auto it : active) {
if(g[it].size() > 1) {
allOne = false;
break;
}
}
if(allOne) {
for(auto it : edges) {
finalColours[it.second] = 1;
}
return 1;
}
g[l + r + 1].resize(0);
g[l + r + 2].resize(0);
int cnt = m;
for(auto it : active) {
if(g[it].size() & 1) {
if(it <= l) {
g[l + r + 1].push_back({it, cnt});
g[it].push_back({l + r + 1, cnt});
} else {
g[l + r + 2].push_back({it, cnt});
g[it].push_back({l + r + 2, cnt});
}
used[cnt] = false;
cnt ++;
}
}
if(g[l + r + 1].size() & 1) {
g[l + r + 1].push_back({l + r + 2, cnt});
g[l + r + 2].push_back({l + r + 1, cnt});
used[cnt] = false;
}
for(int i = 0; i <= l + r + 2; i ++) {
for(auto it : g[i]) {
if(i > it.first) {continue;}
}
}
for(auto it : active) {
if(!gotThrough[it]) {
dfs(it, 0);
}
}
vector<pair<pair<int, int>, int> > lft, rght;
for(auto it : edges) {
if(in[it.second]) {
lft.push_back(it);
} else {
rght.push_back(it);
}
}
int lftAns = solve(lft), rghtAns = solve(rght);
for(auto it : rght) {
finalColours[it.second] += lftAns;
}
return lftAns + rghtAns;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> l >> r >> m;
vector<pair<pair<int, int>, int> > edges;
for(int i = 0; i < m; i ++) {
int a, b;
cin >> a >> b;
edges.push_back({{a, b + l}, i});
}
int ret = solve(edges);
cout << ret << endl;
for(int i = 0; i < m; i ++) {
cout << finalColours[i] << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12140 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12140 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
13164 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
13036 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2121 ms |
71664 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2099 ms |
72236 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12031 ms |
74096 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1075 ms |
169680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5583 ms |
72528 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5566 ms |
72620 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
