oj.uz

Submission #99037

# Submission time Handle Problem Language Result Execution time Memory
99037 2019-02-28T07:12:11 Z 크리(#2856, kriii) Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 3 ms 384 KB 
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;

int N; pair<int, int> P[200100]; int C[100100][3];

int find(int *p, int x)
{
	int &n = p[x];
	if (n != x) n = find(p,n);
	return n;
}

struct see{
	see(){
		for (int i=0;i<=N+1;i++) L[i] = R[i] = i;
	}
	int L[100100],R[100100];
	void er(int x)
	{
		L[find(L,x)] = find(L,x-1);
		R[find(R,x)] = find(R,x+1);
	}
	int l(int x, int d)
	{
		if (x - d <= 0) return 0;
		return find(L,x-d);
	}
	int r(int x, int d)
	{
		if (x + d >= N+1) return N+1;
		return find(R,x+d);
	}
};

bool seen[100100][2];
struct inst{
	int cx,cy,px,py,d,t;
	bool operator <(const inst &t) const{
		return d > t.d;
	}
};

int main()
{
	long long ans = 0;

	scanf ("%d",&N);
	for (int i=0;i<N*2;i++){
		scanf ("%d %d",&P[i].first,&P[i].second);
		if (P[i].first < 1) ans += 1 - P[i].first, P[i].first = 1;
		if (P[i].first > N) ans += P[i].first - N, P[i].first = N;
		if (P[i].second < 1) ans += 1 - P[i].second, P[i].second = 1;
		if (P[i].second > 2) ans += P[i].second - 2, P[i].second = 2;
		C[P[i].first][P[i].second-1]++;
	}

	see rem[2];
	priority_queue<inst> Q;
	for (int i=1;i<=N;i++) for (int j=0;j<2;j++) if (C[i][j]){
		Q.push({i,j,i,j,0,0});
		Q.push({i,j,i,!j,1,0});
		Q.push({i,j,i,j,0,1});
		Q.push({i,j,i,!j,1,1});
	}
	while (!Q.empty()){
		auto p = Q.top(); Q.pop();
		if (C[p.cx][p.cy] == 0) continue;
		if (!seen[p.px][p.py]){
			ans += p.d;
			seen[p.px][p.py] = true;
			rem[p.py].er(p.px);
			if (--C[p.cx][p.cy] == 0) continue;
		}
		int nd = p.d - abs(p.cy - p.py) + 1;
		int py = p.py, px = (p.t ? rem[py].l(p.cx,nd) : rem[py].r(p.cx,nd));
		nd = abs(p.cx - px) + abs(p.cy - py);
		if (1 <= px && px <= N) Q.push({p.cx,p.cy,px,py,nd,p.t});
	}

	printf ("%lld\n",ans);

	return 0;
}

Compilation message

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&N);
  ~~~~~~^~~~~~~~~
joi2019_ho_t4.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d",&P[i].first,&P[i].second);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -