oj.uz

Submission #1017056

# Submission time Handle Problem Language Result Execution time Memory
1017056 2024-07-08T19:43:15 Z parsadox2 Ideal city (IOI12_city) C++17
100 / 100
 92 ms 23972 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 1 ms 5548 KB Output is correct
6 Correct 1 ms 5468 KB Output is correct
7 Correct 1 ms 5468 KB Output is correct
8 Correct 1 ms 5468 KB Output is correct
9 Correct 1 ms 5468 KB Output is correct
10 Correct 1 ms 5468 KB Output is correct
11 Correct 1 ms 5468 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5468 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 2 ms 5616 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 3 ms 5724 KB Output is correct
6 Correct 3 ms 5724 KB Output is correct
7 Correct 3 ms 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 3 ms 5724 KB Output is correct
10 Correct 3 ms 5724 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8584 KB Output is correct
2 Correct 16 ms 8584 KB Output is correct
3 Correct 38 ms 13248 KB Output is correct
4 Correct 36 ms 13256 KB Output is correct
5 Correct 76 ms 21292 KB Output is correct
6 Correct 73 ms 21184 KB Output is correct
7 Correct 74 ms 21440 KB Output is correct
8 Correct 77 ms 21220 KB Output is correct
9 Correct 74 ms 21180 KB Output is correct
10 Correct 78 ms 23228 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 9084 KB Output is correct
2 Correct 19 ms 9080 KB Output is correct
3 Correct 41 ms 14528 KB Output is correct
4 Correct 41 ms 14024 KB Output is correct
5 Correct 85 ms 23812 KB Output is correct
6 Correct 92 ms 22176 KB Output is correct
7 Correct 90 ms 23972 KB Output is correct
8 Correct 81 ms 22204 KB Output is correct
9 Correct 77 ms 21948 KB Output is correct
10 Correct 84 ms 21856 KB Output is correct