Submission #1017056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017056		parsadox2	Ideal city (IOI12_city)	C++17	100 / 100	92 ms	23972 KiB

city

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N = 1e5 + 10 , mod = 1e9;

int n;
long long ans;

struct Tree{
	vector <int> adj[N];
	int ar[N] , pos;
	Tree()
	{
		pos = 1;
		ar[1] = 1;
	}
	void Add_Edge(int id)
	{
		if(!adj[id].empty() && adj[id].back() == pos)
			return;
		adj[id].push_back(pos);
		adj[pos].push_back(id);
	}
	void Solve(int v = 1 , int p = -1)
	{
		for(auto u : adj[v])  if(u != p)
		{
			Solve(u , v);
			ar[v] += ar[u];
			ans = (ans + 1LL * ar[u] * (n - ar[u]) % mod) % mod;
			//cout << u << " " << ar[u] << " " << (n - ar[u]) << endl;
		}
	}
	/*void Debug()
	{
		cout << pos << endl;
		for(int i = 1 ; i <= pos ; i++)
			cout << ar[i] << " ";
		cout << endl;
		for(int i = 1 ; i <= pos ; i++)  for(auto u : adj[i])
			cout << i << " ---- " << u << endl;
	}*/
} row , col;

int DistanceSum(int nn, int *X, int *Y)
{
	n = nn;
	vector <pair<int , int>> r , c;
	for(int i = 0 ; i < n ; i++)
	{
		r.push_back({X[i] , Y[i]});
		c.push_back({Y[i] , X[i]});
	}
	sort(r.begin() , r.end());
	sort(c.begin() , c.end());
	map <pair <int , int> , int> mpr , mpc;
	mpr[r[0]] = 1;
	mpc[c[0]] = 1;
	for(int i = 1 ; i < n ; i++)
	{
		if(r[i].F == r[i - 1].F && r[i].S == r[i - 1].S + 1)
			row.ar[row.pos]++;
		else
		{
			row.pos++;
			row.ar[row.pos] = 1;
		}
		if(c[i].F == c[i - 1].F && c[i].S == c[i - 1].S + 1)
			col.ar[col.pos]++;
		else
		{
			col.pos++;
			col.ar[col.pos] = 1;
		}
		mpr[r[i]] = row.pos;
		mpc[c[i]] = col.pos;
		if(mpr.find(make_pair(r[i].F - 1 , r[i].S)) != mpr.end())
			row.Add_Edge(mpr[make_pair(r[i].F - 1 , r[i].S)]);
		if(mpc.find(make_pair(c[i].F - 1 , c[i].S)) != mpc.end())
			col.Add_Edge(mpc[make_pair(c[i].F - 1 , c[i].S)]);
	}
	row.Solve();
	col.Solve();
	return ans;
}

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