Submission #525868

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
525868	2022-02-13T04:28:30 Z	koioi.org-koosaga	Mountains and Valleys (CCO20_day1problem3)	C++17	Compilation error	0 ms	0 KB

Main

#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 f[20][MAXN], far[MAXN], diam[MAXN], pfar[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]];
		}
	}
	{
		// TODO: n^2
		for(int i = 0; i < n; i++){
			if(dep[i] >= 2){
				vis[i] = 1;
				vis[par[1][i]] = 1;
				auto x = dfsl(par[0][i]);
				g[i] = x.first;
				f[0][i] = dfsl(x.second).first;
				vis[i] = 0;
				vis[par[1][i]] = 0;
			}
		}
		// TODO: n^2
		for(int i = 0; i < n; i++){
			vis[i] = 1;
			for(auto &j : gph[i]){
				subDiams[i].emplace_back(dfsl(dfsl(j).second).first, j);
			}
			sort(all(subDiams[i]));
			reverse(all(subDiams[i]));
			vis[i] = 0;
		}
		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]]);
			}
		}
		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]));
		}
	}
	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 + sz(v));
		}
		if(l != x.e){
			maxPath = max(maxPath, diam[x.e] - 3 + sz(v));
		}
		{
			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 + sz(v));
		}
		// TODO: qn.
		vector<int> valup, valdown;
		if(v.s != l) valup.push_back(far[v.s]);
		if(v.e != l) valdown.push_back(far[v.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, d + 1);
				break;
			}
			valup.push_back(dist);
		}
		{
			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

Main.cpp: In function 'int main()':
Main.cpp:110:5: error: 'g' was not declared in this scope
  110 |     g[i] = x.first;
      |     ^
Main.cpp:168:46: error: 'v' was not declared in this scope
  168 |    maxPath = max(maxPath, diam[x.s] - 3 + sz(v));
      |                                              ^
Main.cpp:2:22: note: in definition of macro 'sz'
    2 | #define sz(v) ((int)(v).size())
      |                      ^
Main.cpp:171:46: error: 'v' was not declared in this scope
  171 |    maxPath = max(maxPath, diam[x.e] - 3 + sz(v));
      |                                              ^
Main.cpp:2:22: note: in definition of macro 'sz'
    2 | #define sz(v) ((int)(v).size())
      |                      ^
Main.cpp:188:45: error: 'v' was not declared in this scope
  188 |    maxPath = max(maxPath, new_diam - 3 + sz(v));
      |                                             ^
Main.cpp:2:22: note: in definition of macro 'sz'
    2 | #define sz(v) ((int)(v).size())
      |                      ^
Main.cpp:192:6: error: 'v' was not declared in this scope
  192 |   if(v.s != l) valup.push_back(far[v.s]);
      |      ^
Main.cpp:193:6: error: 'v' was not declared in this scope
  193 |   if(v.e != l) valdown.push_back(far[v.e]);
      |      ^
Main.cpp:194:73: error: 'g' was not declared in this scope
  194 |   for(int i = x.s; dep[i] >= dep[l] + 2; i = par[0][i]) valup.push_back(g[i]);
      |                                                                         ^
Main.cpp:195:75: error: 'g' was not declared in this scope
  195 |   for(int i = x.e; dep[i] >= dep[l] + 2; i = par[0][i]) valdown.push_back(g[i]);
      |                                                                           ^
Main.cpp:200:27: error: no matching function for call to 'max(int&, std::tuple_element<0, std::pair<long long int, long long int> >::type)'
  200 |     dist = max(dist, 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:200:27: 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'})
  200 |     dist = max(dist, 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:200:27: 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'})
  200 |     dist = max(dist, 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:200:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  200 |     dist = max(dist, 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:200:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  200 |     dist = max(dist, d + 1);
      |                           ^
Main.cpp:207:25: error: 'val' was not declared in this scope; did you mean 'valup'?
  207 |    for(auto &i : valup) val.push_back(i);
      |                         ^~~
      |                         valup
Main.cpp:208:27: error: 'val' was not declared in this scope; did you mean 'valup'?
  208 |    for(auto &i : valdown) val.push_back(i);
      |                           ^~~
      |                           valup
Main.cpp:211:25: error: 'val' was not declared in this scope; did you mean 'valup'?
  211 |   for(int i = 0; i < sz(val); i++){
      |                         ^~~
Main.cpp:2:22: note: in definition of macro 'sz'
    2 | #define sz(v) ((int)(v).size())
      |                      ^