fork download
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define all(x) begin(x),end(x)
  4. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  5. template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
  6. #define debug(a) cerr << "(" << #a << ": " << a << ")\n";
  7. typedef long long ll;
  8. typedef unsigned long long ull;
  9. typedef vector<int> vi;
  10. typedef vector<vi> vvi;
  11. typedef pair<int,int> pi;
  12. const int mxN = 1e5+1, oo = 1e9;
  13. map<string,int> artistmap;
  14. typedef array<char,4> state;
  15. unordered_map<ull,char> from[2][100];
  16. vector<state> states[2][100];
  17. vi adj[2][100];
  18. int a[100];
  19. ull getid(const state& s) {
  20. ull res=0;
  21. for(int i=0;i<4;++i) res|=((ull)s[i])<<(i*8);
  22. return res;
  23. }
  24. void dfs(state s, int at, int d=0, bool rev=false) {
  25. if(d==4) return;
  26. s[0] = a[at];
  27. sort(all(s));
  28. auto id = getid(s);
  29. for(int to : adj[rev][at]) {
  30. if(find(all(s),a[to])==s.end()) {
  31. if(!from[rev][to].count(id)) {
  32. if(d==3) states[rev][to].push_back(s);
  33. from[rev][to][id]=at;
  34. dfs(s,to,d+1,rev);
  35. }
  36. }
  37. }
  38. }
  39. void reconstruct(state s, int at, bool rev=false) {
  40. vi ans;
  41. for(int i=0;i<4;++i) {
  42. int fr = from[rev][at][getid(s)];
  43. for(int j=0;j<4;++j) if(s[j]==a[fr]) s[j]=0;
  44. sort(all(s));
  45. ans.push_back(fr+1);
  46. at=fr;
  47. }
  48. if(!rev) reverse(all(ans));
  49. cout << ans;
  50. }
  51. int main() {
  52. int n; cin >> n;
  53. for(int i=0;i<n;++i) {
  54. string s; cin >> s;
  55. if(!artistmap.count(s)) artistmap[s]=artistmap.size()+1;
  56. a[i]=artistmap[s];
  57. int k; cin >> k;
  58. for(int j=0;j<k;++j) {
  59. int to; cin >> to,to--;
  60. if(a[to]!=a[i]) {
  61. adj[0][i].push_back(to);
  62. adj[1][to].push_back(i);
  63. }
  64. }
  65. }
  66. for(int i=0;i<n;++i) {
  67. dfs({}, i);
  68. dfs({},i,0,true);
  69. }
  70. vi order(n); iota(all(order),0);
  71. random_shuffle(all(order));
  72. for(int i:order) {
  73. unordered_map<ull,int> cnt;
  74. int total=states[0][i].size();
  75. cnt.reserve(total*3);
  76. for(auto s : states[0][i]) {
  77. for(int j=0;j<16;++j) {
  78. auto ss = s;
  79. for(int k=0;k<4;++k) if(j&(1<<k)) {
  80. ss[k]=0;
  81. }
  82. sort(all(ss));
  83. cnt[getid(ss)]++;
  84. }
  85. }
  86. for(auto s : states[1][i]) {
  87. int cur = total;
  88. for(int j=0;j<15;++j) {
  89. auto ss = s;
  90. int odd=0;
  91. for(int k=0;k<4;++k) if(j&(1<<k)) {
  92. ss[k]=0;
  93. odd^=1;
  94. }
  95. sort(all(ss));
  96. // inclusion exclusion
  97. cur+=(1-2*odd)*cnt[getid(ss)];
  98. }
  99. if(cur) {
  100. for(auto t : states[0][i]) {
  101. bool found=true;
  102. for(auto c : s) for(auto cc : t) if(c==cc) {
  103. found=false;
  104. break;
  105. }
  106. if(!found) continue;
  107. reconstruct(t,i);
  108. cout << ' ' << i+1 << ' ';
  109. reconstruct(s,i,true);
  110. cout << '\n';
  111. exit(0);
  112. }
  113. assert(false);
  114. }
  115.  
  116. }
  117. }
  118. cout << "fail\n";
  119. }
Success #stdin #stdout 0s 5676KB
stdin
10
a 2 10 3
b 1 6
c 2 1 5
d 1 9
e 1 4
f 1 2
g 2 6 8
h 0
i 1 3
j 1 7
stdout
5 4 9 3 1 10 7 6 2