# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1070961 | 2024-08-22T21:53:41 Z | HorizonWest | Closing Time (IOI23_closing) | C++17 | 1000 ms | 1593956 KB |
//#include "closing.h" #include <iostream> #include <complex> #include <iomanip> #include <vector> #include <algorithm> #include <functional> #include <bitset> #include <queue> #include <map> #include <stack> #include <cmath> #include <cstdint> #include <cassert> using namespace std; #define ll unsigned long long #define fs first #define sd second const ll Inf = 1e18 + 7; vector <ll> bfs(int n, int x, vector <vector<pair<ll, ll>>> v) { vector <ll> D(n + 1, Inf); queue <int> q; q.push(x); D[x] = 0; while (!q.empty()) { int x = q.front(); q.pop(); for(auto& u : v[x]) if(D[u.fs] == Inf) { D[u.fs] = D[x] + u.sd; q.push(u.fs); } } return D; } vector <int> line(int n, int x, int y, vector <vector<pair<ll, ll>>> v) { vector <int> p(n, -1), s; queue <int> q; q.push(x); p[x] = x; while (!q.empty()) { int x = q.front(); q.pop(); for(auto& u : v[x]) if(p[u.fs] == -1) { p[u.fs] = x; q.push(u.fs); } } while (true) { s.push_back(y); if(y == x) break; y = p[y]; } reverse(s.begin(), s.end()); return s; } int max_score(int n, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) { vector <vector<pair<ll, ll>>> v(n + 1, vector <pair<ll, ll>> ()); map <int, map <int, int>> mp; for(int i = 0; i < n - 1; i++) { mp[U[i]][V[i]] = W[i]; mp[V[i]][U[i]] = W[i]; v[U[i]].push_back({ V[i], W[i] }); v[V[i]].push_back({ U[i], W[i] }); } vector <ll> d1 = bfs(n, X, v), d2 = bfs(n, Y, v); vector <int> s = line(n, X, Y, v), sz(n), p(n); int ans = 0, m = s.size(); auto S = [&](auto S, int node, int parent) -> int { if(sz[node] != 0) return sz[node]; sz[node] = 2; for(auto& u : v[node]) if(u.fs != parent){ sz[node] += S(S, u.fs, node); } return sz[node]; }; auto F = [&] (auto F, int node, int parent) -> vector <vector<ll>> { //cerr << node << endl; return { { } }; vector <vector<ll>> dp1(2 * S(S, node, parent) + 1, vector <ll> (3, Inf)); dp1[1][0] = d1[node]; dp1[1][1] = d2[node]; dp1[2][2] = max(d1[node], d2[node]); for(auto& u : v[node]) if(u.fs != parent) { vector <vector<ll>> dp2 = F(F, u.fs, node); for(int j = dp1.size() - 1; j >= 0; j--) { for(int k = 0; k < dp2.size(); k++) if(j - k >= 0) { dp1[j][0] = min(dp1[j][0], dp1[j - k][0] + dp2[k][0]); dp1[j][1] = min(dp1[j][1], dp1[j - k][1] + dp2[k][1]); dp1[j][2] = min(dp1[j][2], dp1[j - k][2] + min(dp2[k][2], min(dp2[k][0], dp2[k][1]))); } } } return dp1; }; vector <vector<vector<ll>>> dp(m, vector <vector<ll>> (2 * n + 1, vector <ll> (4, Inf))); for(int i = 0; i < m; i++){ dp[i][0][0] = dp[i][0][1] = dp[i][0][2] = 0; p[s[i]] = 1; //cerr << d1[s[i]] << " " << d2[s[i]] << " " << s[i] << endl; } dp[0][1][0] = d1[s[0]]; dp[0][1][1] = d2[s[0]]; dp[0][2][2] = max(d1[s[0]], d2[s[0]]); for(int i = 0; i < m; i++) { if(i > 0){ int w = mp[s[i-1]][s[i]]; for(int j = 0; j <= 2 * n; j++){ if(j > 0) dp[i][j][0] = min(dp[i][j][0], dp[i-1][j-1][0] + d1[s[i]]); // X -> i if(j > 0) dp[i][j][1] = min(dp[i][j][1], dp[i-1][j-1][1] + d2[s[i]]); // Y -> i if(j > 0) dp[i][j][1] = min(dp[i][j][1], dp[i-1][j-1][2] + d2[s[i]]); if(j > 0) dp[i][j][1] = min(dp[i][j][1], dp[i-1][j-1][3] + d2[s[i]]); if(j > 1) dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-2][0] + max(d1[s[i]], d2[s[i]])); // X, Y -> i if(j > 1) dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-2][2] + max(d1[s[i]], d2[s[i]])); dp[i][j][3] = min(dp[i][j][3], dp[i-1][j][3]); dp[i][j][3] = min(dp[i][j][3], dp[i][j][0]); } } for(auto& u : v[s[i]]) if(p[u.fs] == 0) { vector <vector<ll>> dp1 = F(F, u.fs, s[i]); /*cerr << "Node: " << s[i] << " -> " << u.fs << endl; for(int j = 0; j < dp1.size(); j ++){ cerr << j << ": " << (dp1[j][0] == Inf ? -1 : dp1[j][0]) << " " << (dp1[j][1] == Inf ? -1 : dp1[j][1]) << " " << (dp1[j][2] == Inf ? -1 : dp1[j][2]) << endl; }*/ for(int j = 2*n; j >= 0; j--) { for(int k = 0; k < dp1.size(); k++) if(j - k >= 0) { dp[i][j][0] = min(dp[i][j][0], dp[i][j - k][0] + dp1[k][0]); dp[i][j][1] = min(dp[i][j][1], dp[i][j - k][1] + dp1[k][1]); dp[i][j][2] = min(dp[i][j][2], dp[i][j - k][2] + min(dp1[k][2], min(dp1[k][0], dp1[k][1]))); } dp[i][j][3] = min(dp[i][j][3], dp[i][j][0]); } } /*cerr << "Node: " << s[i] << " -> " << i << endl; for(int j = 0; j < dp[i].size(); j ++){ cerr << j << ": " << (dp[i][j][0] == Inf ? -1 : dp[i][j][0]) << " " << (dp[i][j][1] == Inf ? -1 : dp[i][j][1]) << " " << (dp[i][j][2] == Inf ? -1 : dp[i][j][2]) << endl; }*/ } for(int i = 0; i <= 2*n; i++) { for(int j = 0; j < 4; j++) if(dp[m-1][i][j] <= K){ ans = i; } } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1153 ms | 1593956 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 600 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Incorrect | 1 ms | 600 KB | 1st lines differ - on the 1st token, expected: '44', found: '52' |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 600 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Incorrect | 1 ms | 600 KB | 1st lines differ - on the 1st token, expected: '44', found: '52' |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 600 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Incorrect | 1 ms | 600 KB | 1st lines differ - on the 1st token, expected: '44', found: '52' |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 600 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 344 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 1 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 600 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Incorrect | 1 ms | 600 KB | 1st lines differ - on the 1st token, expected: '44', found: '52' |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 600 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Incorrect | 1 ms | 600 KB | 1st lines differ - on the 1st token, expected: '44', found: '52' |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 600 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Incorrect | 1 ms | 600 KB | 1st lines differ - on the 1st token, expected: '44', found: '52' |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 600 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Incorrect | 1 ms | 600 KB | 1st lines differ - on the 1st token, expected: '44', found: '52' |
12 | Halted | 0 ms | 0 KB | - |