Submission #370729

#TimeUsernameProblemLanguageResultExecution timeMemory
370729aZvezdaTeoretičar (COCI18_teoreticar)C++14
0 / 130
12031 ms169680 KiB
#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 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...
#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...