Submission #525874

#TimeUsernameProblemLanguageResultExecution timeMemory
525874koioi.org-koosagaMountains and Valleys (CCO20_day1problem3)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() using namespace std; typedef long long lint; typedef pair<lint, lint> pi; const int MAXN = 500005; struct edge{ int s, e, x; }; int n, m; vector<int> gph[MAXN]; int par[20][MAXN], dep[MAXN]; int lca(int x, int y){ if(dep[x] > dep[y]) swap(x, y); int dx = dep[y] - dep[x]; for(int i = 0; dx; i++){ if(dx & 1) y = par[i][y]; dx >>= 1; } for(int i = 19; i >= 0; i--){ if(par[i][x] != par[i][y]){ x = par[i][x]; y = par[i][y]; } } if(x != y) return par[0][x]; return x; } vector<int> ord; int din[MAXN], dout[MAXN], piv; int far[MAXN], diam[MAXN], pfar[MAXN], pdiam[MAXN]; int f[20][MAXN], g[MAXN]; vector<pi> fars[MAXN]; vector<pi> subDiams[MAXN]; int fPathMax(int x, int v){ int ans = -1e9; for(int i = 0; v; i++){ if(v & 1){ ans = max(ans, f[i][x]); x = par[i][x]; } v >>= 1; } return ans; } bool in(int u, int v){ return din[u] <= din[v] && dout[v] <= dout[u]; } void dfs(int x, int p = -1){ ord.push_back(x); din[x] = ++piv; for(auto &y : gph[x]){ if(y == p) continue; par[0][y] = x; dep[y] = dep[x] + 1; dfs(y, x); } dout[x] = piv; } bool vis[MAXN]; pi dfsl(int x, int p = -1){ pi ret(0, x); for(auto &y : gph[x]){ if(y == p || vis[y]) continue; auto ans = dfsl(y, x); ans.first++; ret = max(ret, ans); } return ret; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; vector<edge> qry; for(int i = 0; i < m; i++){ int s, e, x; cin >> s >> e >> x; if(x == 1){ gph[s].push_back(e); gph[e].push_back(s); } else{ qry.push_back({s, e, x}); } } dfs(0); for(int i = 1; i < 20; i++){ for(int j = 0; j < n; j++){ par[i][j] = par[i-1][par[i-1][j]]; } } { reverse(all(ord)); for(auto &i : ord){ for(auto &j : gph[i]){ if(j == par[0][i]) continue; far[i] = max(far[i], far[j] + 1); diam[i] = max({diam[i], diam[j], far[j] + 1}); fars[i].emplace_back(far[j], j); } sort(all(fars[i])); reverse(all(fars[i])); if(sz(fars[i]) >= 2) diam[i] = max(diam[i], (int)fars[i][0].first + (int)fars[i][1].first + 2); } reverse(all(ord)); for(auto &i : ord){ if(i == 0) continue; for(auto &j : fars[par[0][i]]){ if(j.second == i) continue; pfar[i] = j.first + 1; break; } fars[i].emplace_back(pfar[i], par[0][i]); sort(all(fars[i])); reverse(all(fars[i])); } for(auto &i : ord){ if(i == 0) continue; for(auto &[d, v] : subDiams[par[0][i]]){ if(v == i) continue; pdiam[i] = max(pdiam[i], (int)d); break; } { int new_diam = 0; int cnt = 0; for(auto &[d, v] : fars[par[0][i]]){ if(v == i) continue; new_diam += d + 1; cnt += 1; if(cnt == 2) break; } pdiam[i] = max(pdiam[i], new_diam); } for(auto &j : gph[i]){ if(j == par[0][i]) subDiams[i].emplace_back(pdiam[i], j); else subDiams[i].emplace_back(diam[j], j); } sort(all(subDiams[i])); reverse(all(subDiams[i])); } for(int i = 0; i < n; i++){ if(dep[i] >= 2){ int cnt = 0; for(auto &[d, v] : fars[par[0][i]]){ if(v == i || v == par[1][i]) continue; g[i] = max(g[i], d + 1); f[0][i] += d + 1; cnt++; if(cnt == 2) break; } for(auto &[d, v] : subDiams[par[0][i]]){ if(v == i || v == par[1][i]) continue; f[0][i] = max(f[0][i], d + 1); break; } } } for(int i = 1; i < 20; i++){ for(int j = 0; j < n; j++){ f[i][j] = max(f[i-1][j], f[i-1][par[i-1][j]]); } } } int ans = 2 * n - 2 - diam[0]; for(auto &x : qry){ int l = lca(x.s, x.e); int plen = dep[x.s] + dep[x.e] - 2 * dep[l] + 1; int maxPath = -1e9; if(dep[x.s] >= dep[l] + 2){ maxPath = max(maxPath, fPathMax(x.s, dep[x.s] - dep[l] - 1) - 3 + plen); } if(dep[x.e] >= dep[l] + 2){ maxPath = max(maxPath, fPathMax(x.e, dep[x.e] - dep[l] - 1) - 3 + plen); } if(l != x.s){ maxPath = max(maxPath, diam[x.s] - 3 + plen); } if(l != x.e){ maxPath = max(maxPath, diam[x.e] - 3 + plen); } { int new_diam = 0; int cnt = 0; // passes through l for(auto &[d, v] : fars[l]){ if((in(v, x.s) || in(v, x.e)) && v != par[0][l]) continue; new_diam += d + 1; cnt += 1; if(cnt == 2) break; } for(auto &[d, v] : subDiams[l]){ if((in(v, x.s) || in(v, x.e)) && v != par[0][l]) continue; new_diam = max(new_diam, (int)d); break; } maxPath = max(maxPath, new_diam - 3 + plen); } // TODO: qn. vector<int> valup, valdown; if(x.s != l) valup.push_back(far[x.s]); if(x.e != l) valdown.push_back(far[x.e]); for(int i = x.s; dep[i] >= dep[l] + 2; i = par[0][i]) valup.push_back(g[i]); for(int i = x.e; dep[i] >= dep[l] + 2; i = par[0][i]) valdown.push_back(g[i]); { int dist = 0; for(auto &[d, v] : fars[l]){ if((in(v, x.s) || in(v, x.e)) && v != par[0][l]) continue; dist = max(dist, (int)d + 1); break; } valup.push_back(dist); } vector<int> val; { reverse(all(valdown)); for(auto &i : valup) val.push_back(i); for(auto &i : valdown) val.push_back(i); } int pmax = -1e9; for(int i = 0; i < sz(val); i++){ maxPath = max(maxPath, sz(val) - 1 - i + val[i] + pmax); pmax = max(pmax, i + val[i]); } ans = min(ans, 2 * n - 4 + x.x - maxPath); } cout << ans << endl; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:159:28: error: no matching function for call to 'max(int&, std::tuple_element<0, std::pair<long long int, long long int> >::type)'
  159 |      g[i] = max(g[i], d + 1);
      |                            ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
Main.cpp:159:28: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::pair<long long int, long long int> >::type' {aka 'long long int'})
  159 |      g[i] = max(g[i], d + 1);
      |                            ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
Main.cpp:159:28: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::pair<long long int, long long int> >::type' {aka 'long long int'})
  159 |      g[i] = max(g[i], d + 1);
      |                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
Main.cpp:159:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  159 |      g[i] = max(g[i], d + 1);
      |                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
Main.cpp:159:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  159 |      g[i] = max(g[i], d + 1);
      |                            ^
Main.cpp:166:34: error: no matching function for call to 'max(int&, std::tuple_element<0, std::pair<long long int, long long int> >::type)'
  166 |      f[0][i] = max(f[0][i], d + 1);
      |                                  ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
Main.cpp:166:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::pair<long long int, long long int> >::type' {aka 'long long int'})
  166 |      f[0][i] = max(f[0][i], d + 1);
      |                                  ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
Main.cpp:166:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::tuple_element<0, std::pair<long long int, long long int> >::type' {aka 'long long int'})
  166 |      f[0][i] = max(f[0][i], d + 1);
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
Main.cpp:166:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  166 |      f[0][i] = max(f[0][i], d + 1);
      |                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
Main.cpp:166:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  166 |      f[0][i] = max(f[0][i], d + 1);
      |                                  ^