oj.uz

Submission #83068

# Submission time Handle Problem Language Result Execution time Memory
83068 2018-11-04T17:22:06 Z edenooo Ideal city (IOI12_city) C++17
32 / 100
 22 ms 7272 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

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 += (ll)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]; //이걸 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)
{
	NN = N;
	x.clear();
	for (int i = 0; i < 100101; i++) s[i].clear();
	cnt = vector<int>(100101);
	for (int i = 0; i < 100101; i++) g[i].clear();
	sub = vector<int>(100101);
	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;
}

int DistanceSum(int N, int *X, int *Y)
{
	ll answer = 0;
	answer += f(N, X, Y);
	answer += f(N, Y, X);
	return answer % 1'000'000'000;
}

Compilation message

city.cpp: In function 'int DFS(int, int)':
city.cpp:30: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:52: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:97:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (a < s[i - 1].size() && b < s[i].size())
          ~~^~~~~~~~~~~~~~~~~
city.cpp:97: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 6264 KB Output is correct
2 Correct 8 ms 6268 KB Output is correct
3 Correct 8 ms 6344 KB Output is correct
4 Correct 9 ms 6548 KB Output is correct
5 Correct 8 ms 6548 KB Output is correct
6 Correct 11 ms 6548 KB Output is correct
7 Correct 9 ms 6548 KB Output is correct
8 Correct 9 ms 6548 KB Output is correct
9 Correct 9 ms 6692 KB Output is correct
10 Correct 9 ms 6692 KB Output is correct
11 Correct 10 ms 6692 KB Output is correct

Subtask #2
21.0 / 21.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 7088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 7272 KB Output isn't correct
2 Halted 0 ms 0 KB -