제출 #241828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241828		johutha	이상적인 도시 (IOI12_city)	C++17	100 / 100	182 ms	17456 KiB

city

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

#define int int64_t
#define mod 1000000000

using namespace std;

struct tree
{
	int n = 0;
	int totsz = 0;
	int res = 0;
	vector<vector<int>> adjlist;
	vector<int> vsz;

	int dfs(int curr, int par)
	{
		int sz = vsz[curr];
		for (auto next : adjlist[curr])
		{
			if (next == par) continue;
			sz += dfs(next, curr);
		}

		res += (sz*(totsz - sz)) % mod;
		res %= mod;

		return sz;
	}

	void addsz(int v)
	{
		vsz[v]++;
		totsz++;
	}

	int addvertex()
	{
		n++;
		adjlist.push_back(vector<int>());
		vsz.push_back(0);
		addsz(n - 1);
		return n - 1;
	}

	void addedge(int a, int b)
	{
		adjlist[b].push_back(a);
		adjlist[a].push_back(b);
	}
};

int moves(int n, vector<pair<int,int>> pnts)
{
	sort(pnts.begin(), pnts.end());
	map<int,map<int,int>> mp;

	tree t;

	for (int i = 0; i < n; i++)
	{
		int y = pnts[i].first;
		int x = pnts[i].second;
		if (i > 0 && y == pnts[i - 1].first && x - 1 == pnts[i - 1].second)
		{
			mp[y][x] = mp[y][x - 1];
			t.addsz(mp[y][x]);
			if (mp[y - 1].find(x) == mp[y - 1].end()) continue;
			if (mp[y - 1].find(x - 1) != mp[y - 1].end()) continue;
			t.addedge(mp[y][x], mp[y-1][x]);
			continue;
		}
		mp[y][x] = t.addvertex();
		if (mp[y - 1].find(x) == mp[y - 1].end()) continue;
		t.addedge(mp[y][x], mp[y - 1][x]);
	}

	t.dfs(0, -1);
	return t.res;
}

signed DistanceSum(signed n, signed *X, signed *Y)
{
	vector<pair<int,int>> pnts(n);
	for (int i = 0; i < n; i++) pnts[i] = make_pair(X[i], Y[i]);

	int res = moves(n, pnts);
	for (int i = 0; i < n; i++) swap(pnts[i].first, pnts[i].second);
	res += moves(n, pnts);

	return res % mod;
}

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