# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
965945 | 2024-04-19T08:32:43 Z | phoenix0423 | Fun Tour (APIO20_fun) | C++17 | 1 ms | 348 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define fastio ios::sync_with_stdio(false), cin.tie(0) #pragma GCC optimize("Ofast") #define pb push_back #define eb emplace_back #define f first #define s second #define q1 hoursRequired #define q2 attrationsBehind #include "fun.h" const int maxn = 500 + 5; const int INF = 1e9; vector<int> adj[maxn]; int dist[maxn][maxn]; vector<int> sol1(int n){ for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(dist[i][j] != 1) dist[i][j] = INF; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(q1(i, j) == 1){ dist[i][j] = dist[j][i] = 1; } } } for(int k = 0; k < n; k++){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } vector<int> ans; for(int i = 0; i < n; i++){ vector<int> use(n); ans.pb(i); use[i] = 1; while(ans.size() < n){ int mx = -1, lst = INF, prv = i; for(int j = 0; j < n; j++){ if(use[j]) continue; if(dist[prv][j] <= lst){ if(mx == -1 || dist[prv][j] > dist[prv][mx]) mx = j; } } if(mx == -1) break; use[mx] = 1, ans.pb(mx); lst = dist[prv][mx]; prv = mx; } if(ans.size() == n) return ans; } return vector<int>(); } std::vector<int> createFunTour(int n, int Q) { if(n <= 500) return sol1(n); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Tour is not fun |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Tour is not fun |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Tour is not fun |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Tour is not fun |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Tour is not fun |
2 | Halted | 0 ms | 0 KB | - |