Submission #1222063

#TimeUsernameProblemLanguageResultExecution timeMemory
1222063monaxia꿈 (IOI13_dreaming)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> // #include <ext/random> // #include <ext/pb_ds/assoc_container.hpp> #pragma GCC optimize("O3,unroll-loops") #pragma GCC optimize ("Ofast") #define pb push_back #define ppb pop_back #define fr first #define sc second #define all(v) v.begin(), v.end() #define all1(v) v.begin() + 1, v.begin() + n + 1 using namespace std; // using namespace __gnu_pbds; using ll = long long; using ull = unsigned long long; using ld = long double; constexpr uint64_t Mod = 1e9 + 7; constexpr ld eps = 1e-9; constexpr int sqr = 447; int n = 2e5; ll ans = 0; vector <ll> val(n + 1); vector <vector <pair <int ,int>>> graph(n + 1); vector <vector <int>> p(n + 5, vector <int> (40, -1)); vector <int> h(n + 1, 0), v(n + 1, 0); void dfs1111(int node, int pr){ h[node] = h[pr] + 1; p[node][0] = pr; for(auto& x : graph[node]){ if(x.fr == pr) continue; dfs1111(x.fr, node); } } void preprocess(){ dfs1111(1, 0); for(int j = 1; 1 << j <= n; j ++){ for(int i = 1; i <= n; i ++){ if(p[i][j - 1] != -1) p[i][j] = p[p[i][j - 1]][j - 1]; } } } int lca(int u, int v){ if(h[u] < h[v]) swap(u, v); while(h[u] > h[v]){ u = p[u][__lg(h[u] - h[v])]; } if(u == v) return u; for(int i = __lg(n); i >= 1; i --){ if(p[u][i] != p[v][i]){ u = p[u][i]; v = p[v][i]; } } while(u != v){ u = p[u][0]; v = p[v][0]; } return u; } vector <gp_hash_table <int, ll>> cnt(n + 1), total(n + 1); vector <multiset <ll>> value(n + 1); ll mn = LLONG_MAX, mx = LLONG_MIN; void dfs1(int node, int p){ v[node] = 1; for(auto& x : graph[node]){ if(x.fr == p) continue; dfs1(x.fr, node); total[node][x.fr] += total[x.fr][x.fr]; total[node][node] = max(total[node][node], total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc); value[node].insert(total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc); } } void dfs(int node, int p, int d){ if(p){ auto w = value[p].rbegin(); if(cnt[node][node] * d + total[node][node] == total[p][p]) w ++; total[node][node] = max(total[node][node], *w + d); value[node].insert(*w + d); // cout << node << ' ' << *w << " " << d << "\n"; // cout << node << " " << p << " " << cnt[p][p] - cnt[p][node] << " " << (cnt[p][p] - cnt[p][node]) * d << "\n"; } auto test = value[node].end(); test ++; mn = min(mn, total[node][node]); mx = max(mx, total[node][node]); for(auto& x : graph[node]){ if(x.fr == p) continue; dfs(x.fr, node, x.sc); } } void solve(){ ll n, m, l; cin >> n >> m >> l; for(int i = 1; i <= m; i ++){ int u, v, d; cin >> u >> v >> d; u ++; v ++; // cout << u << ' ' << v << " " << d << "\n"; graph[u].pb({v, d}); graph[v].pb({u, d}); } for(int i = 1; i <= n; i ++) cnt[i][i] = 1, value[i].insert(0); vector <ll> ans; for(int i = 1; i <= n; i ++){ if(v[i]) continue; dfs1(i, 0); dfs(i, 0, 0); ans.pb(mn); // for(int j = 1; j <= n; j ++) cout << v[j] << ' '; cout << "\n"; // cout << mn << '\n'; mn = LLONG_MAX; // cout << "\n"; } // for(int i = 1; i <= n; i ++){ // for(int j = 1; j <= n; j ++) cout << total[i][j] << ' '; cout << '\n'; // } cout << "\n"; // for(int i = 1; i <= n; i ++){ // for(int j = 1; j <= n; j ++) cout << cnt[i][j] << ' '; cout << '\n'; // } sort(all(ans), greater <> ()); for(int i = 1; i < ans.size(); i ++) ans[i] += l; sort(all(ans), greater <> ()); // for(auto& x : ans) cout << x << ' '; if(ans.size() > 1) cout << max(mx, ans[0] + ans[1]); else cout << max(mx, ans[0]); } signed main() { cin.tie(0)->sync_with_stdio(0); ll n = 1; // cin >> n; while(n) { solve(); n --; cout << "\n"; } cerr << "t elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; }

Compilation message (stderr)

dreaming.cpp:79:9: error: 'gp_hash_table' was not declared in this scope
   79 | vector <gp_hash_table <int, ll>> cnt(n + 1), total(n + 1);
      |         ^~~~~~~~~~~~~
dreaming.cpp:79:31: error: template argument 1 is invalid
   79 | vector <gp_hash_table <int, ll>> cnt(n + 1), total(n + 1);
      |                               ^~
dreaming.cpp:79:31: error: template argument 2 is invalid
dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:89:14: error: invalid types 'int[int]' for array subscript
   89 |         total[node][x.fr] += total[x.fr][x.fr];
      |              ^
dreaming.cpp:89:35: error: invalid types 'int[int]' for array subscript
   89 |         total[node][x.fr] += total[x.fr][x.fr];
      |                                   ^
dreaming.cpp:91:14: error: invalid types 'int[int]' for array subscript
   91 |         total[node][node] = max(total[node][node], total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc);
      |              ^
dreaming.cpp:91:38: error: invalid types 'int[int]' for array subscript
   91 |         total[node][node] = max(total[node][node], total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc);
      |                                      ^
dreaming.cpp:91:57: error: invalid types 'int[int]' for array subscript
   91 |         total[node][node] = max(total[node][node], total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc);
      |                                                         ^
dreaming.cpp:91:75: error: invalid types 'int[int]' for array subscript
   91 |         total[node][node] = max(total[node][node], total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc);
      |                                                                           ^
dreaming.cpp:93:33: error: invalid types 'int[int]' for array subscript
   93 |         value[node].insert(total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc);
      |                                 ^
dreaming.cpp:93:51: error: invalid types 'int[int]' for array subscript
   93 |         value[node].insert(total[x.fr][x.fr] + cnt[x.fr][x.fr] * x.sc);
      |                                                   ^
dreaming.cpp: In function 'void dfs(int, int, int)':
dreaming.cpp:101:15: error: invalid types 'int[int]' for array subscript
  101 |         if(cnt[node][node] * d + total[node][node] == total[p][p]) w ++;
      |               ^
dreaming.cpp:101:39: error: invalid types 'int[int]' for array subscript
  101 |         if(cnt[node][node] * d + total[node][node] == total[p][p]) w ++;
      |                                       ^
dreaming.cpp:101:60: error: invalid types 'int[int]' for array subscript
  101 |         if(cnt[node][node] * d + total[node][node] == total[p][p]) w ++;
      |                                                            ^
dreaming.cpp:102:14: error: invalid types 'int[int]' for array subscript
  102 |         total[node][node] = max(total[node][node], *w + d);
      |              ^
dreaming.cpp:102:38: error: invalid types 'int[int]' for array subscript
  102 |         total[node][node] = max(total[node][node], *w + d);
      |                                      ^
dreaming.cpp:114:23: error: invalid types 'int[int]' for array subscript
  114 |     mn = min(mn, total[node][node]);
      |                       ^
dreaming.cpp:115:23: error: invalid types 'int[int]' for array subscript
  115 |     mx = max(mx, total[node][node]);
      |                       ^
dreaming.cpp: In function 'void solve()':
dreaming.cpp:140:37: error: invalid types 'int[int]' for array subscript
  140 |     for(int i = 1; i <= n; i ++) cnt[i][i] = 1, value[i].insert(0);
      |                                     ^