oj.uz

Submission #83071

# Submission time Handle Problem Language Result Execution time Memory
83071 2018-11-04T18:19:42 Z edenooo Ideal city (IOI12_city) C++17
100 / 100
 95 ms 19936 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<string>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<math.h>
#include<algorithm>
using namespace std;

#define INF 987654321
#define ll long long
#define MOD 1'000'000'000

int A[100101], B[100101];

vector<pair<int, int> > x; //x y
vector<pair<pair<int, int>, int> > s[100101]; //start end n
vector<int> cnt(100101), g[100101], sub(100101);
ll sum, res;
int h, NN;

int DFS(int n, int prev)
{
	sub[n] = cnt[n];
	sum += 1LL * h * cnt[n];
	h++;

	for (int i = 0; i < g[n].size(); i++)
	{
		int next = g[n][i];
		if (next == prev) continue;

		sub[n] += DFS(next, n);
	}

	h--;
	return sub[n];
}

void DFS2(int n, int prev, ll sum2) //sum2를 전역에 박았다가 틀림, 바꾸다가 ll을 int로 써서 틀림
{
	if (n != 0)
	{
		sum2 -= sub[n];
		sum2 += NN - sub[n]; //NN을 sum으로 했다가 틀림
	}

	res += sum2 * cnt[n]; //cnt[n]을 안 곱해 줘서 틀림

	for (int i = 0; i < g[n].size(); i++)
	{
		int next = g[n][i];
		if (next == prev) continue;

		DFS2(next, n, sum2);
	}
}

int f(int N, int *X, int *Y) //사실 (y,x)로 X와 Y가 바뀌어 있다.
{
	NN = N;
	x.clear();
	for (int i = 0; i < 100101; i++) s[i].clear();
	cnt = vector<int>(100101, 0);
	for (int i = 0; i < 100101; i++) g[i].clear();
	sub = vector<int>(100101, 0);
	sum = 0, res = 0, h = 0;

	for (int i = 0; i < N; i++)
		x.push_back({ X[i], Y[i] });
	sort(x.begin(), x.end());

	int ord = 0, xx = 0, ss = x[0].second; //정점 생성
	cnt[ord]++;
	for (int i = 1; i < N; i++)
	{
		if (!(x[i].first == x[i - 1].first && x[i].second - 1 == x[i - 1].second)) //새로 만들어진 정점마다 start, end를 저장해 두면 정점끼리 연결되었는지를 쉽게 판단할 수 있다.
		{
			s[xx].push_back({ {ss, x[i - 1].second}, ord });

			ord++;
			ss = x[i].second;
		}

		if (x[i].first != x[i - 1].first)
			xx++;

		cnt[ord]++;
	}
	s[xx].push_back({ {ss, x[N - 1].second}, ord }); //항상 마지막 그룹은 따로 처리해줘야 한다.

	for (int i = 1; i <= xx; i++) //그래프 생성
	{
		int a = 0, b = 0;
		while (a < s[i - 1].size() && b < s[i].size())
		{
			int as = s[i - 1][a].first.first, ae = s[i - 1][a].first.second, an = s[i - 1][a].second;
			int bs = s[i][b].first.first, be = s[i][b].first.second, bn = s[i][b].second;
			if (as <= be && bs <= ae)
			{
				g[an].push_back(bn);
				g[bn].push_back(an);

				if (ae <= be) a++;
				else b++;
			}
			else if (as > be) b++;
			else a++;
		}
	}
	
	DFS(0, -1);
	DFS2(0, -1, sum);

	return (res / 2) % MOD; //여기를 MOD 안 해줘서 틀림
}

int DistanceSum(int N, int *X, int *Y)
{
	ll answer = 0;
	answer += f(N, X, Y);
	answer += f(N, Y, X);

	return answer % MOD;
}

Compilation message

city.cpp: In function 'int DFS(int, int)':
city.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[n].size(); i++)
                  ~~^~~~~~~~~~~~~
city.cpp: In function 'void DFS2(int, int, long long int)':
city.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[n].size(); i++)
                  ~~^~~~~~~~~~~~~
city.cpp: In function 'int f(int, int*, int*)':
city.cpp:98:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (a < s[i - 1].size() && b < s[i].size())
          ~~^~~~~~~~~~~~~~~~~
city.cpp:98:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (a < s[i - 1].size() && b < s[i].size())
                                 ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6248 KB Output is correct
2 Correct 9 ms 6260 KB Output is correct
3 Correct 9 ms 6336 KB Output is correct
4 Correct 8 ms 6412 KB Output is correct
5 Correct 8 ms 6488 KB Output is correct
6 Correct 8 ms 6504 KB Output is correct
7 Correct 8 ms 6504 KB Output is correct
8 Correct 8 ms 6504 KB Output is correct
9 Correct 8 ms 6504 KB Output is correct
10 Correct 8 ms 6504 KB Output is correct
11 Correct 8 ms 6520 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6520 KB Output is correct
2 Correct 9 ms 6520 KB Output is correct
3 Correct 10 ms 6520 KB Output is correct
4 Correct 9 ms 6520 KB Output is correct
5 Correct 10 ms 6524 KB Output is correct
6 Correct 9 ms 6524 KB Output is correct
7 Correct 10 ms 6524 KB Output is correct
8 Correct 10 ms 6648 KB Output is correct
9 Correct 9 ms 6648 KB Output is correct
10 Correct 9 ms 6648 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7144 KB Output is correct
2 Correct 18 ms 7272 KB Output is correct
3 Correct 33 ms 7948 KB Output is correct
4 Correct 31 ms 8348 KB Output is correct
5 Correct 58 ms 10120 KB Output is correct
6 Correct 61 ms 10908 KB Output is correct
7 Correct 62 ms 11740 KB Output is correct
8 Correct 58 ms 12488 KB Output is correct
9 Correct 66 ms 13208 KB Output is correct
10 Correct 69 ms 17032 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 17032 KB Output is correct
2 Correct 21 ms 17032 KB Output is correct
3 Correct 40 ms 17032 KB Output is correct
4 Correct 39 ms 17032 KB Output is correct
5 Correct 72 ms 17316 KB Output is correct
6 Correct 64 ms 17316 KB Output is correct
7 Correct 77 ms 19016 KB Output is correct
8 Correct 66 ms 19016 KB Output is correct
9 Correct 95 ms 19136 KB Output is correct
10 Correct 59 ms 19936 KB Output is correct