Submission #1239964

#TimeUsernameProblemLanguageResultExecution timeMemory
1239964madamadam3Sphinx's Riddle (IOI24_sphinx)C++20
0 / 100
0 ms412 KiB
#include "sphinx.h" #include <bits/stdc++.h> using namespace std; using vi =vector<int>; using vvi =vector<vi>; #define pb push_back #define lb lower_bound #define ub upper_bound #define FOR(i, a, b) for (int i = a; i < b; i++) #define all(x) (x).begin(), (x).end() #define bg(x) (x).begin() #define en(x) (x).end() #define sz(x) int((x).size()) #define rev(x) reverse(all(x)) #define srt(x) sort(all(x)) #define each(a, x) for (auto &a : x) struct DSU { int n; vi par, siz; DSU() {}; DSU(int N) { n = N; siz.assign(n, 1); par.resize(n); iota(all(par), 0); } int find(int v) { if (par[v] == v) return v; return par[v] = find(par[v]); } void unite(int a, int b) { a = find(a); b = find(b); if (a != b) { if (siz[b] > siz[a]) swap(a, b); par[b] = a; siz[a] += siz[b]; } } }; int n, m; vi x, y; vvi adj; vi find_colours(int N, vi X, vi Y) { n = N; m = sz(X); x = X; y = Y; adj.assign(n, vi()); FOR(i, 0, m) adj[x[i]].pb(y[i]), adj[y[i]].pb(x[i]); vi graph(n, n); auto dsu = DSU(n); int cur_colour = 0; FOR(i, 0, n-1) { int colour = graph[i] != n ? graph[i] : cur_colour++; vi test(n, n); test[i] = test[i+1] = -1; int thresh = i > 0 && i < n - 2 ? 3 : 2; if (perform_experiment(test) <= thresh) { graph[i] = graph[i+1] = colour; } else { graph[i] = colour; } } if (graph[n-1] == n) graph[n-1] = cur_colour; // FOR(i, 0, n) { // FOR(col, 0, n) { // vi test(n, col); test[i] = -1; // if (perform_experiment(test) == 1) { // graph[i] = col; // // cout << "node " << i << " has colour " << col << "\n"; // break; // } // } // } return graph; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...