Submission #1225614

#TimeUsernameProblemLanguageResultExecution timeMemory
1225614PagodePaivaSphinx's Riddle (IOI24_sphinx)C++20
1.50 / 100
8 ms452 KiB
#include "sphinx.h" #include<bits/stdc++.h> using namespace std; const int N = 256; int cor[N]; vector <int> g[N]; int t = 0; int mark[N]; void dfs_comp(int v){ mark[v] = 1; for(auto x : g[v]){ if(mark[x]) continue; dfs_comp(x); } return; } void dfs(int v){ cor[v] = t; for(auto x : g[v]){ if(cor[x] != -1) continue; dfs(x); } } std::vector<int> find_colours(int n, std::vector<int> X, std::vector<int> Y) { for(int i = 0;i < X.size();i++){ vector <int> v; for(int j = 0;j < n;j++){ if(j == X[i] or j == Y[i]) v.push_back(-1); else v.push_back(n); } memset(mark, 0, sizeof mark); mark[X[i]] = mark[Y[i]] = 1; int cnt = 0; for(int j = 0;j < n;j++){ if(mark[j] == 0){ cnt++; dfs(j); } } int check = perform_experiment(v); if(check != cnt+2){ g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } } memset(cor, -1, sizeof cor); vector <int> ans; for(int i = 0;i < n;i++){ if(cor[i] == -1){ dfs(i); t++; } ans.push_back(cor[i]); } return ans; }
#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...