Codeforces 429E Points and Segments
前4問は何だったのかという感じの良問。
問題概要: 区間がN個与えられる。この区間たちに 1 or -1 を割り当てて、どの座標でもそれを含む区間の値の和の絶対値が 1 以下になるようなものを構成せよ。
解法: まず全座標がdistinctなときにできるなら適当に順番を決めればdistinctじゃなくてもできる。
全座標がdistinctなとき、条件は区間が偶数個重なっているところ全てで和が 0 であることと同値。座標を前から見て、区間が消えたり現れたりするのを 2 つごとに見ると、
であることが必要十分なことがわかる。
これを満たす割り当てがあるかどうかだが、関係があるところにそれっぽく辺をはると(区間の始点/終点のどちらを見てはられた辺かを考えると)これは偶サイクルっぽい感じ(性格には、「違うパリティ」の辺が偶数本)なことがわかるので、必ず割り当てがある。解けた。
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; #define SIZE 200000 class unionfind { public: int par[SIZE]; int ran[SIZE]; int ren[SIZE]; void init() { for (int i = 0; i<SIZE; i++) { par[i] = i; ran[i] = 0; ren[i] = 1; } } int find(int a) { if (a == par[a])return a; else return par[a] = find(par[a]); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b)return; if (ran[a]>ran[b]) { par[b] = a; ren[a] += ren[b]; } else { par[a] = b; ren[b] += ren[a]; } if (ran[a] == ran[b])ran[b]++; } }; unionfind uf; typedef pair<int, int>pii; typedef pair<pii, int>pi3; bool flag[200000]; int main() { int num; scanf("%d", &num); vector<pi3>vec; for (int i = 0; i < num; i++) { int za, zb; scanf("%d%d", &za, &zb); vec.push_back(make_pair(make_pair(za, 0), i)); vec.push_back(make_pair(make_pair(zb, 1), i)); } sort(vec.begin(), vec.end()); uf.init(); for (int i = 0; i < num; i++) { if (vec[i * 2].first.second == vec[i * 2 + 1].first.second) { uf.unite(vec[i * 2].second * 2, vec[i * 2 + 1].second * 2 + 1); uf.unite(vec[i * 2].second * 2 + 1, vec[i * 2 + 1].second * 2); } else { uf.unite(vec[i * 2].second * 2, vec[i * 2 + 1].second * 2); uf.unite(vec[i * 2].second * 2 + 1, vec[i * 2 + 1].second * 2 + 1); } } for (int i = 0; i < num; i++) { if (i * 2 == uf.find(i * 2)) { if (!flag[uf.find(i * 2 + 1)]) { flag[i * 2] = true; } } if (i * 2 + 1 == uf.find(i * 2 + 1)) { if (!flag[uf.find(i * 2)]) { flag[i * 2 + 1] = true; } } //printf("%d %d\n", uf.find(i * 2), uf.find(i * 2 + 1)); } for (int i = 0; i < num; i++) { if (flag[uf.find(i * 2)])printf("0 "); else printf("1 "); } printf("\n"); }