# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
277513 | 2020-08-21T05:33:55 Z | 임성재(#5118) | Travelling Salesperson (CCO20_day2problem1) | C++17 | 7000 ms | 25376 KB |
#include<bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(false); cin.tie(0); #define fi first #define se second #define em emplace #define eb emplace_back #define mp make_pair #define all(v) (v).begin(), (v).end() typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int inf = 1e9; const ll INF = 1e18; int n; int g[2010][2010]; vector<int> ans, v; void f(int r) { ans.clear(); int s = r == 1 ? 2 : 1; ans.eb(s); int m = s; for(int i=1; i<=n; i++) { if(i == r || i == s) continue; v.clear(); bool flag = false; for(int j=0; j<ans.size(); j++) { if(!flag && ans[j] == m) { flag = true; if(g[m][i] == 1) { v.eb(m); v.eb(i); if(j+1 < ans.size() && g[i][ans[j+1]] == 1) m = ans[j+1]; else m = i; } else { v.eb(i); v.eb(m); if(j-1 >= 0 && g[i][ans[j-1]] == 2) m = ans[j-1]; else m = i; } } else v.eb(ans[j]); } ans = v; } if(g[ans.front()][ans.back()] == 2) { reverse(ans.begin()+1, ans.end()); reverse(all(ans)); } if(g[ans.back()][r] == 1) reverse(ans.begin(), ans.end()-1); reverse(all(ans)); cout << ans.size() + 1 << "\n"; cout << r << " "; for(auto i : ans) { cout << i << " "; } cout << "\n"; } int main() { fast; cin >> n; for(int i=2; i<=n; i++) { string s; cin >> s; for(int j=1; j<i; j++) { g[i][j] = g[j][i] = (s[j-1] == 'R') + 1; } } for(int i=1; i<=n; i++) { f(i); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 0 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 0 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Execution timed out | 7020 ms | 25376 KB | Time limit exceeded |
17 | Halted | 0 ms | 0 KB | - |