Submission #415860

#	Time	Username	Problem	Language	Result	Execution time	Memory
415860		KalasLavas	Ideal city (IOI12_city)	C++14	100 / 100	490 ms	21808 KiB

city

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//#undef LOCALKL
#define IO \
ios_base::sync_with_stdio(0);(cin).tie(0);(cout).tie(0)
#define y1 y1_
#define prev prev_
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#ifdef LOCALKL
#define cerr cerr<<"\33[1;32m"
#define cout cout<<"\33[0m"
#else
#define endl '\n'
#define cerr if(1){}else cerr
#endif
#define OK cout<<"OK\n"<<endl;
#define setpre(k) fixed<<setprecision(k)
#define mmset(k,y) memset(k,y,sizeof(k))
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using pll = pair<long long,long long>;
using ull = unsigned long long;
using intt = long long;
using ll = long long;
using ld = long double;

const ll m9 = 998244353;
const ll m7 = 1000000007;
const ll m18 = 1000000000000000000;
const ll i127 = 2139062143;
const ll l127 = 9187201950435737471;
/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/
ll ans, n;
map<pii, bool>g, c;
 
ll dfs(int x, int y)
{
	int xl=x, xr=x;
 
	c[{x, y}]=1;
	while(g[{xl-1, y}]) c[{--xl, y}]=1;
	while(g[{xr+1, y}]) c[{++xr, y}]=1;
	
	ll val=xr-xl+1;
	for(int xx=xl; xx<=xr; xx++)
		for(int yy=y-1;yy<=y+1;yy+=2)
			if(g[{xx, yy}] and !c[{xx, yy}])
				val+=dfs(xx, yy);
 
	ans = (ans + val * (n-val)) % 1000000000;
	return val;
}

int DistanceSum(int N, int *X, int *Y)
{
	n = N;
	int minx=INT_MAX, miny=INT_MAX;
	for(int i=0;i<n;i++)
	{
		minx = min(minx, X[i]);
		miny = min(miny, Y[i]);
	}
	minx--; miny--;
 
	for(int i=0;i<n;i++) g[{X[i]-minx,Y[i]-miny}]=1;
	dfs(g.begin()->F.F, g.begin()->F.S);
	
	g.clear(); c.clear();
	for(int i=0;i<n;i++) g[{Y[i]-miny,X[i]-minx}]=1;
	dfs(g.begin()->F.F, g.begin()->F.S);
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45