Submission #1177694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177694		madamadam3	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	0 ms	412 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
using vi = vector<int>; 
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

void trace_vec(vi &inp) {
  for (auto &el : inp) cout << el << " ";
  cout << "\n";
}

int N, M;
vector<set<int>> adj;
vi G;

int queryTwo(int a, int b, int colourA, int colourB) {
  vi E(N, N);
  E[a] = colourA;
  E[b] = colourB;

  return perform_experiment(E);
}

void findColour(int a) {
  if (G[a] != -1) return;

  int neighbour = *adj[a].begin();
  int CCs = queryTwo(a, neighbour, -1, -1) - 1;

  for (int colour = 0; colour < N; colour++) {
    int x1 = queryTwo(a, neighbour, colour, -1) - 1;
    int x2 = queryTwo(a, neighbour, -1, colour) - 1;

    if (CCs == 1 && x1 == 1) {
      G[a] = G[neighbour] = colour;
      break;
    } else if (x1 == 1) {
      G[neighbour] = colour;
    } else if (x2 == 1) {
      G[a] = colour;
    }
  }
}

void findFrom(int a, int b) {
  if (G[a] == -1) return;
  if (G[b] != -1) return;
  if (adj[a].count(b) == 0) return;

  int baseline = queryTwo(a, b, -1, -1);

  for (int colour = 0; colour < N; colour++) {
    int x = queryTwo(a, b, colour, -1);
    if (x < baseline) {
      G[b] = colour;
      break;
    } else if (x > baseline) {
      G[b] = G[a];
      break;
    }
  }
}

vi find_colours(int _N, vi X, vi Y) {
  N = _N, M = (int) X.size();

  adj.assign(N, set<int>());
  for (int i = 0; i < M; i++) {
    adj[X[i]].insert(Y[i]);
    adj[Y[i]].insert(X[i]);
  }
  
  G.assign(N, -1);
  int start = 0;
  for (int i = 0; i < N; i++) {
    if (adj[i].size() == 1) start = i;
  }

  if (N == 2) { // 3/100 pts
    findColour(start);
    return G;
  } else if (N <= 50) {
    set<int> vis;
    queue<int> q;
    q.push(start);
    findColour(start);

    while (!q.empty()) {
      int cur = q.front();
      q.pop();

      // cout << "visited " << cur << "\n";

      vis.insert(cur);

      for (int v : adj[cur]) {
        if (vis.count(v)) continue;
        findFrom(cur, v);
        q.push(v);
      }

      // cout << "colour is: " << G[cur] << "\n";
    }

    return G; 
  }


  return G;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36