Submission #727264

#TimeUsernameProblemLanguageResultExecution timeMemory
727264TigerpantsSenior Postmen (BOI14_postmen)C++17
55 / 100
569 ms143648 KiB
#include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> #include <numeric> #include <functional> #include <unordered_set> using namespace std; typedef long long int ll; typedef vector<ll> vll; typedef set<ll> sll; typedef vector<vll> vvll; typedef vector<sll> vsll; typedef vector<bool> vb; typedef unordered_set<ll> usll; typedef vector<usll> vusll; #define rep(i, a, b) for (ll i = a; i < b; i++) #define mp(a, b) make_pair(a, b) #define pb(a) push_back(a) #define sz(a) a.size() ll N, M; vsll g; vll S; vb onS; vvll paths; bool DFS(ll cur) { if (onS[cur]) { // found axon paths.pb(vll()); paths.back().pb(cur); onS[cur] = false; return true; } else { onS[cur] = true; S.pb(cur); for (sll::iterator nxt = g[cur].begin(); nxt != g[cur].end();) { g[*nxt].erase(cur); if (DFS(*nxt)) { if (onS[cur]) { paths.back().pb(cur); onS[cur] = false; S.pop_back(); g[cur].erase(nxt); return true; } else { onS[cur] = true; } } nxt++; g[cur].erase(prev(nxt)); } S.pop_back(); return false; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> M; g.resize(N); rep(i, 0, M) { ll tmpa, tmpb; cin >> tmpa >> tmpb; tmpa--; tmpb--; g[tmpa].insert(tmpb); g[tmpb].insert(tmpa); } onS.resize(N, false); rep(i, 0, N) { DFS(i); } for (vvll::iterator path = paths.begin(); path != paths.end(); path++) { for (vll::iterator itr = path->begin(); itr != path->end(); itr++) { cout << (*itr) + 1 << " "; } cout << "\n"; } cout << flush; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...