Submission #1079025

#TimeUsernameProblemLanguageResultExecution timeMemory
1079025GraySimurgh (IOI17_simurgh)C++17
0 / 100
2 ms348 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; #define ll int #define ff first #define ss second #define ln "\n" #define ld long double vector<pair<ll, ll>> e; vector<vector<ll>> A; ll n, m; // slow version vector<ll> ans; void dfs(ll u, vector<bool> &vis, vector<ll> &cur, ll lev){ vis[u]=1; if (lev==n){ ll res=count_common_roads(cur); // cout << e[cur[0]].ff << " "; // for (auto ch:cur) cout << e[ch].ss << ' '; // cout << " : "; // cout << res << ln; if (res==n-1) {ans=cur; return;} } for (auto i:A[u]){ ll v = e[i].ff^e[i].ss^u; if (!vis[v]){ cur.push_back(i); dfs(v, vis, cur, lev+1); cur.pop_back(); if (ans.size()) return; } } vis[u]=0; } vector<int> find_roads(int _n, vector<int> u, vector<int> v) { n=_n; m=u.size(); e.resize(m); A.clear(); A.resize(n); for (ll i=0; i<m; i++){ e[i]={u[i], v[i]}; A[u[i]].push_back(i); A[v[i]].push_back(i); } vector<bool> vis(n); vector<ll> cur; for (ll i=0; i<n and !ans.size(); i++){ vis.assign(n, 0); cur.clear(); dfs(i, vis, cur, 1); } assert(ans.size()); 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...