Submission #546919

#TimeUsernameProblemLanguageResultExecution timeMemory
546919fvogel499Roller Coaster Railroad (IOI16_railroad)C++17
0 / 100
912 ms85140 KiB
/* * File created on 04/08/2022 at 21:58:56. * Link to problem: * Description: * Time complexity: O() * Space complexity: O() * Status: --- * Copyright: Ⓒ 2022 Francois Vogel */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <functional> using namespace std; using namespace __gnu_pbds; #define pii pair<int, int> #define f first #define s second #define vi vector<int> #define all(x) x.begin(), x.end() #define size(x) (int)((x).size()) #define pb push_back #define ins insert #define cls clear #define int ll #define ll long long #define ld long double typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; int plan_roller_coaster_act(vi from, vi to) { set<int> av; for (int i : from) av.ins(i); for (int i : to) av.ins(i); map<int, int> compress; int kc = 0; for (int i : av) compress[i] = kc++; for (int i = 0; i < size(from); i++) from[i] = compress[from[i]]; for (int i = 0; i < size(to); i++) to[i] = compress[to[i]]; int n = size(compress); vi graph [n]; vi revG [n]; for (int i = 0; i < size(from); i++) { graph[from[i]].pb(to[i]); revG[to[i]].pb(from[i]); } int sum = 0; for (int i = 0; i < n-1; i++) { sum += size(graph[i])-size(revG[i]); if (sum > 1) return 1; for (int j = 1; j < sum; j++) { sum++; graph[i].pb(i+1); revG[i+1].pb(i); } } bool vis [n]; for (int i = 0; i < n; i++) vis[i] = false; queue<int> q; q.push(0); vis[0] = true; while (!q.empty()) { int x = q.front(); q.pop(); for (int y : graph[x]) if (!vis[y]) { vis[y] = true; q.push(y); } for (int y : revG[x]) if (!vis[y]) { vis[y] = true; q.push(y); } } // for (int i = 0; i < n; i++) if (!vis[i]) return 1; return 0; } int plan_roller_coaster(vector<signed> from, vector<signed> to) { vi ifrom, ito; for (int i : from) ifrom.pb(i); for (int i : to) ito.pb(i); return plan_roller_coaster_act(ifrom, ito); } // signed main() { // cin.tie(0); // ios_base::sync_with_stdio(0); // int n; // cin >> n; // vector<signed> from(n), to(n); // for (int i = 0; i < n; i++) cin >> from[i]; // for (int i = 0; i < n; i++) cin >> to[i]; // cout << plan_roller_coaster(from, to) << endl; // cout.flush(); // int d = 0; // d++; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...