fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. #define all(c) (c).begin(), (c).end()
  4. #define pb push_back
  5. #define FOR(i,a,b) for( ll i = (ll)(a); i <= (ll)(b); i++ )
  6. #define ROF(i,a,b) for( ll i = (ll)(a); i >= (ll)(b); i-- )
  7. #define debug(x) cerr << "[DEBUG] " << #x << " = " << x << endl;
  8. #define matrix vector< vector<ll> >
  9. #define F first
  10. #define S second
  11. #define mp make_pair
  12. #define INPFILE freopen("input.in","r",stdin)
  13. #define OUTFILE freopen("output.out","w",stdout)
  14. #define BOOST ios_base::sync_with_stdio(false); cin.tie(NULL)
  15. using namespace std;
  16.  
  17. ll parent[70];
  18. ll ans[70];
  19. set<tuple<ll,ll,ll>> rules;
  20.  
  21. ll find(ll x) {
  22.   if(x == parent[x]) return x;
  23.   return parent[x] = find(parent[x]);
  24. }
  25.  
  26. void join(ll x, ll y) {
  27.   ll p = find(x);
  28.   ll q = find(y);
  29.  
  30.   if(p == q) return;
  31.  
  32.   parent[p] = q;
  33. }
  34.  
  35. void reset() {
  36.   FOR(i,0,69) parent[i] = i;
  37. }
  38.  
  39. bool rec(set<ll> Q,  ll last) {
  40.   //debug(last);
  41.   //for(ll x : Q) cerr << x << ' ';
  42.   //cerr << '\n';
  43.   if(Q.empty()) return true;
  44.   set<tuple<ll,ll,ll>> v;
  45.   for(auto p : rules) {
  46.     ll x = get<0>(p);
  47.     ll y = get<1>(p);
  48.     ll z = get<2>(p);
  49.  
  50.     bool hasx = Q.find(x) != Q.end();
  51.     bool hasy = Q.find(y) != Q.end();
  52.     bool hasz = Q.find(z) != Q.end();
  53.  
  54.     if(hasz && (!hasx || !hasy)) return false;
  55.     else if(hasz || (hasx && hasy)) v.insert(p);
  56.   }
  57.  
  58.   for(ll cur : Q) {
  59.     reset();
  60.     bool pos = true;
  61.     for(auto p : v) {
  62.       ll x = get<0>(p);
  63.       ll y = get<1>(p);
  64.       ll z = get<2>(p);
  65.  
  66.       if(cur != z) {
  67.         join(x, z);
  68.         join(y, z);
  69.       }
  70.       if((cur == x || cur == y) && cur != z) {
  71.         pos = false;
  72.         break;
  73.       }
  74.     }
  75.     for(auto p : v) {
  76.       ll x = get<0>(p);
  77.       ll y = get<1>(p);
  78.       ll z = get<2>(p);
  79.  
  80.       if(cur == z && find(x) == find(y)) {
  81.         pos = false;
  82.         break;
  83.       }
  84.     }
  85.  
  86.     if(pos) {
  87.       map<ll,set<ll>> grp;
  88.       for(ll x : Q) if(x != cur) {
  89.         grp[find(x)].insert(x);
  90.       }
  91.       ans[cur] = last;
  92.       bool ret = true;
  93.       for(auto it : grp) {
  94.         ret &= rec(it.S, cur);
  95.       }
  96.       return ret;
  97.     }
  98.   }
  99.  
  100.   return false;
  101. }
  102.  
  103. int main() {
  104.   ll _t, _c = 1; cin >> _t;
  105.   while(_t--) {
  106.     FOR(i,0,69) ans[i] = -1;
  107.     rules.clear();
  108.     ll n, m;
  109.     cin >> n >> m;
  110.  
  111.     while(m--) {
  112.       ll x, y, z;
  113.       cin >> x >> y >> z;
  114.       rules.insert({min(x,y), max(x,y), z});
  115.     }
  116.  
  117.     set<ll> Q;
  118.     FOR(i,1,n) Q.insert(i);
  119.  
  120.     bool ret = rec(Q, 0);
  121.     cout << "Case #" << _c++ << ": ";
  122.     if(!ret) {
  123.       cout << "Impossible\n";
  124.     } else {
  125.       FOR(i,1,n) cout << ans[i] << ' ';
  126.       cout << '\n';
  127.     }
  128.   }
  129. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
6
3 1
1 2 3
3 3
1 2 2
2 3 3
3 1 1
4 2
2 1 2
1 4 3
6 3
2 4 3
6 5 4
1 2 6
7 4
7 3 5
4 1 2
6 3 6
6 4 5
12 9
1 5 7
11 2 6
9 4 12
8 12 6
10 1 7
4 3 12
3 10 6
8 11 8
2 5 10
stdout
copy 
Case #1: 3 3 0 
Case #2: Impossible
Case #3: 3 0 2 3 
Case #4: Impossible
Case #5: 2 0 6 5 2 5 5 
Case #6: 7 10 12 12 10 0 6 6 12 7 8 6
https://ideone.com/wc0Spl
language:
C++ 4.3.2 (gcc-4.3.2)
created:
4 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!