fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
5 4 9 3 1 10 7 6 2
https://ideone.com/JEZoNF
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!