Submission #617806

#	Time	Username	Problem	Language	Result	Execution time	Memory
617806		amunduzbaev	Fountain Parks (IOI21_parks)	C++17	Compilation error	0 ms	0 KiB

parks

#include "parks.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;

const int N = 2e5 + 5;
vector<ar<int, 3>> edges[N];

int construct_roads(vector<int> x, vector<int> y) {
	int n = x.size();
	map<ar<int, 2>, int> ss, mm;
	for(int i=0;i<n;i++){
		ss[{x[i], y[i]}] = i;
	}
	
	vector<ar<int, 2>> e, p;
	
	auto add = [&](int a, int b, int p1, int p2){
		edges[a].push_back({b, p1, p2});
		edges[b].push_back({a, p1, p2});
	};
	
	for(int i=0;i<n;i++){
		if(ss.count({x[i] - 2, y[i]})){
			int j = ss[{x[i] - 2, y[i]}];
			e.push_back({i, j});
			p.push_back({-1, -1});
			int u = e.size() - 1;
			if(mm.count({x[i] - 1, y[i] - 1})){
				int v = mm[{x[i] - 1, y[i] - 1}];
				add(u, v, x[i] - 1, y[i] - 1);
				mm.erase({x[i] - 1, y[i] - 1});
			} else {
				mm[{x[i] - 1, y[i] - 1}] = u;
			}
			if(mm.count({x[i] - 1, y[i] + 1})){
				int v = mm[{x[i] - 1, y[i] + 1}];
				add(u, v, x[i] - 1, y[i] + 1);
				mm.erase({x[i] - 1, y[i] + 1});
			} else {
				mm[{x[i] - 1, y[i] + 1}] = u;
			}
		}
		if(ss.count({x[i], y[i] - 2})){
			int j = ss[{x[i], y[i] - 2}];
			e.push_back({i, j});
			p.push_back({-1, -1});
			int u = e.size() - 1;
			if(mm.count({x[i] - 1, y[i] - 1})){
				int v = mm[{x[i] - 1, y[i] - 1}];
				add(u, v, x[i] - 1, y[i] - 1);
				mm.erase({x[i] - 1, y[i] - 1});
			} else {
				mm[{x[i] - 1, y[i] - 1}] = u;
			}
			if(mm.count({x[i] + 1, y[i] - 1})){
				int v = mm[{x[i] + 1, y[i] - 1}];
				add(u, v, x[i] + 1, y[i] - 1);
				mm.erase({x[i] + 1, y[i] - 1});
			} else {
				mm[{x[i] + 1, y[i] - 1}] = u;
			}
		}
	}
	
	int m = e.size();
	if(m != n - 1) return 0;
	assert(m == n - 1);
	for(int i=0;i<m;i++){
		assert((int)edges[i].size() <= 2);
	}
	
	for(auto [x, i] : mm){
		p[i] = x;
		assert((int)edges[i].size() < 2):
	}
	
	vector<int> used(m);
	
	function<void(int)> dfs = [&](int i){
		used[i] = 1;
		for(auto [x, p1, p2] : edges[i]){
			if(used[x]) continue;
			p[x] = {p1, p2};
			dfs(x);
		}
	};
	
	for(int i=0;i<m;i++){
		if(used[i]) continue;
		if(p[i][0] == -1){
			assert(edges[i].size() == 2);
			p[i] = {edges[i].back()[1], edges[i].back()[2]};
			edges[i].pop_back();
		}
		
		dfs(i);
	}
	
	vector<int> u(m), v(m), A(m), B(m);
	for(int i=0;i<m;i++){
		u[i] = e[i][0], v[i] = e[i][1];
		A[i] = p[i][0], B[i] = p[i][1];
		assert(~A[i] && ~B[i]);
	}
	
	build(u, v, A, B);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:82:35: error: expected ';' before ':' token
   82 |   assert((int)edges[i].size() < 2):
      |                                   ^