F: Three Kingdoms of Bourdelot
問題
複数のドキュメントがある。各ドキュメントには家系図の情報が複数行書かれている。ドキュメントは正と負の2種類あり、各行はペア(x, y)であり、
- ドキュメントが正の場合：xはyの祖先である
- ドキュメントが負の場合：xはyの祖先ではない
を意味する。
各ドキュメントはそれぞれについて、正か負わからない。n個のドキュメントと二人の人p, qが与えられたとき、pがqの祖先であるような無矛盾なドキュメントの正負の割当があるかどうか判定せよ。
制約
すべての人は互いに異なるただひとつの名前を持つ
ドキュメントの数n <= 1000
各ドキュメントの行数m_i <= 100000
ドキュメント行数の総和 <= 100000
出てくる人名の数 <= 300
解法
ドキュメントが全て負のときは矛盾がない。例えば登場する人が全て兄弟である場合である。pがqの祖先であるためには、行(p, q)を持つドキュメントを正にする必要があり、正にすべきドキュメントが連鎖する。
(x, y)を繋ぐときは、xの祖先の集合とyの子孫の集合をそれぞれ取り、全てのペア(i, j)を列挙し、(i, j)を持つドキュメントを正にしてドキュメントの全ての行をスタックに積む。
計算量について人の数をkとすると、ペア(x, y)はそれぞれ1回だけ繋ぐのでO(min(M, k^2)) (M = sum m)、xの祖先・yの子孫がそれぞれO(k)、ドキュメントを見つけるのにTreeSetを使ってO(log n)。合わせてO(min(M, k^2) k^2 log n + n log n)な気がするが、小さい定数がたくさんついて、枝刈りして良し。計算量不明。
コード
#include<stack> #include<set> #include<map> #include<stdio.h> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<string.h> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } int N; int A, B; char buf[9999]; vector<pair<int, int> > C[1111]; bool use[1111]; bool checked[333][333]; map<string, int> name; int get_id(const string &s) { map<string, int>::iterator it = name.find(s); if (it == name.end()) it = name.insert(make_pair(s, name.size())).first; return it->second; } struct Triple { int a, b, c; Triple() {} Triple(int a_, int b_, int c_) : a(a_), b(b_), c(c_) {} bool operator<(const Triple &y) const { return a != y.a? a < y.a: b != y.b? b < y.b: c < y.c; } }; set<Triple> se; VI up[333], down[333]; int mark[333], mark_cnt; VI ancestor(int x) { VI ret; mark_cnt++; mark[x] = mark_cnt; ret.push_back(x); for (int i=0; i<(int)ret.size(); i++) { EACH (e, up[ret[i]]) { if (mark[*e] != mark_cnt) { mark[*e] = mark_cnt; ret.push_back(*e); } } } return ret; } VI descendant(int x) { VI ret; mark_cnt++; mark[x] = mark_cnt; ret.push_back(x); for (int i=0; i<(int)ret.size(); i++) { EACH (e, down[ret[i]]) { if (mark[*e] != mark_cnt) { mark[*e] = mark_cnt; ret.push_back(*e); } } } return ret; } int main() { scanf("%s", buf); A = get_id(buf); scanf("%s", buf); B = get_id(buf); scanf("%d", &N); REP (i, N) { int m; scanf("%d", &m); C[i].resize(m); REP (j, m) { scanf("%s", buf); C[i][j].first = get_id(buf); scanf("%s", buf); C[i][j].second = get_id(buf); se.insert(Triple(C[i][j].first, C[i][j].second, i)); } } bool yes = true; stack<pair<int, int> > S; S.push(make_pair(A, B)); while (!S.empty()) { int x = S.top().first; int y = S.top().second; S.pop(); if (checked[y][x]) { yes = false; break; } if (checked[x][y]) continue; checked[x][y] = true; VI anc = ancestor(x); VI des = descendant(y); REP (i, anc.size()) REP (j, des.size()) { if (checked[des[j]][anc[i]]) { yes = false; } VI update; set<Triple>::iterator it = se.lower_bound(Triple(anc[i], des[j], -1)); while (it != se.end() && it->a == anc[i] && it->b == des[j]) { if (!use[it->c]) { use[it->c] = true; update.push_back(it->c); } se.erase(it++); } REP (k, update.size()) REP (p, C[update[k]].size()) S.push(C[update[k]][p]); } down[x].push_back(y); up[y].push_back(x); } puts(yes? "Yes": "No"); return 0; }
感想
計算量がわからないので想定解の解説を聞きたかった。
