답안 #169258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169258	2019-12-19T11:11:51 Z	mohammad_kilani	무지개나라 (APIO17_rainbow)	C++17	11 / 100	1146 ms	18296 KB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
vector< int > arr[N];

int n , m;

int cnt = 0 , dsu[N];

int Find(int u){
	return (u == dsu[u] ? u : dsu[u] = Find(dsu[u]));
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	n = R,  m = C;
	arr[sr].push_back(sc);
	for(int i = 0 ;i < M;i++){
		if(S[i] == 'N') sr--; else if(S[i] == 'S') sr++; else if(S[i] == 'E') sc++; else sc--;
		arr[sr].push_back(sc);
	}
	for(int i = 1;i <= R;i++){
		sort(arr[i].begin(),arr[i].end());
		arr[i].resize(unique(arr[i].begin(),arr[i].end()) - arr[i].begin());
	}
}


int colour(int ar, int ac, int br, int bc) {
	int ans = 0 , a , b, j;
	vector< pair<int,int> > pre , cur;
	for(int i = ar ;i <= br;i++){
		j = lower_bound(arr[i].begin(),arr[i].end(), ac) - arr[i].begin();
		a = ac - 1;
		while(j < (int)arr[i].size() && arr[i][j] <= bc){
			if(a + 1 <= arr[i][j] - 1){
				cur.push_back(make_pair(a + 1 , arr[i][j] - 1));
			}
			a = arr[i][j];
			j++;
		}
		if(a + 1 <= bc) cur.push_back(make_pair(a + 1,  bc));
		ans += (int)cur.size();
		for(j = 0 ;j < (int)cur.size();j++){
			dsu[cnt + j] = cnt + j;
		}
		j = 0;
		for(int i = 0;i < (int)cur.size();i++){
			while(j < (int)pre.size() && pre[j].second < cur[i].first) j++;
			while(j < (int)pre.size() && pre[j].first <= cur[i].second){
				a = Find(cnt - (int)pre.size() + j);
				b = Find(cnt + i);
				if(a != b){
					ans--;
					dsu[a] = b;
				}
				j++;
			}
			if(j)
				j--;
		}
		cnt += (int)cur.size();
		pre = cur;
		cur.clear();
	}
    return ans;
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5368 KB	Output is correct
2	Correct	9 ms	5368 KB	Output is correct
3	Correct	8 ms	5240 KB	Output is correct
4	Correct	8 ms	5056 KB	Output is correct
5	Correct	10 ms	5496 KB	Output is correct
6	Correct	6 ms	4988 KB	Output is correct
7	Correct	6 ms	4984 KB	Output is correct
8	Correct	6 ms	4984 KB	Output is correct
9	Correct	6 ms	4984 KB	Output is correct
10	Correct	6 ms	4984 KB	Output is correct
11	Correct	9 ms	5244 KB	Output is correct
12	Correct	10 ms	5372 KB	Output is correct
13	Correct	13 ms	5752 KB	Output is correct
14	Correct	11 ms	5880 KB	Output is correct
15	Correct	11 ms	5112 KB	Output is correct
16	Correct	6 ms	4984 KB	Output is correct
17	Correct	6 ms	5112 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	6 ms	5112 KB	Output is correct
3	Runtime error	1146 ms	14324 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	5112 KB	Output is correct
2	Correct	13 ms	6124 KB	Output is correct
3	Correct	17 ms	8696 KB	Output is correct
4	Correct	16 ms	7216 KB	Output is correct
5	Correct	15 ms	7244 KB	Output is correct
6	Correct	16 ms	6392 KB	Output is correct
7	Correct	17 ms	6392 KB	Output is correct
8	Correct	10 ms	5880 KB	Output is correct
9	Correct	10 ms	5756 KB	Output is correct
10	Correct	9 ms	5496 KB	Output is correct
11	Correct	11 ms	5752 KB	Output is correct
12	Correct	10 ms	5880 KB	Output is correct
13	Correct	15 ms	8440 KB	Output is correct
14	Correct	13 ms	6904 KB	Output is correct
15	Correct	14 ms	7000 KB	Output is correct
16	Correct	16 ms	6264 KB	Output is correct
17	Correct	14 ms	6136 KB	Output is correct
18	Correct	13 ms	6264 KB	Output is correct
19	Correct	15 ms	7412 KB	Output is correct
20	Correct	15 ms	7412 KB	Output is correct
21	Correct	10 ms	5880 KB	Output is correct
22	Correct	11 ms	5880 KB	Output is correct
23	Correct	12 ms	5880 KB	Output is correct
24	Correct	16 ms	6264 KB	Output is correct
25	Correct	16 ms	6640 KB	Output is correct
26	Runtime error	34 ms	18296 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Halted	0 ms	0 KB	-

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5368 KB	Output is correct
2	Correct	9 ms	5368 KB	Output is correct
3	Correct	8 ms	5240 KB	Output is correct
4	Correct	8 ms	5056 KB	Output is correct
5	Correct	10 ms	5496 KB	Output is correct
6	Correct	6 ms	4988 KB	Output is correct
7	Correct	6 ms	4984 KB	Output is correct
8	Correct	6 ms	4984 KB	Output is correct
9	Correct	6 ms	4984 KB	Output is correct
10	Correct	6 ms	4984 KB	Output is correct
11	Correct	9 ms	5244 KB	Output is correct
12	Correct	10 ms	5372 KB	Output is correct
13	Correct	13 ms	5752 KB	Output is correct
14	Correct	11 ms	5880 KB	Output is correct
15	Correct	11 ms	5112 KB	Output is correct
16	Correct	6 ms	4984 KB	Output is correct
17	Correct	6 ms	5112 KB	Output is correct
18	Runtime error	23 ms	13176 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5368 KB	Output is correct
2	Correct	9 ms	5368 KB	Output is correct
3	Correct	8 ms	5240 KB	Output is correct
4	Correct	8 ms	5056 KB	Output is correct
5	Correct	10 ms	5496 KB	Output is correct
6	Correct	6 ms	4988 KB	Output is correct
7	Correct	6 ms	4984 KB	Output is correct
8	Correct	6 ms	4984 KB	Output is correct
9	Correct	6 ms	4984 KB	Output is correct
10	Correct	6 ms	4984 KB	Output is correct
11	Correct	9 ms	5244 KB	Output is correct
12	Correct	10 ms	5372 KB	Output is correct
13	Correct	13 ms	5752 KB	Output is correct
14	Correct	11 ms	5880 KB	Output is correct
15	Correct	11 ms	5112 KB	Output is correct
16	Correct	6 ms	4984 KB	Output is correct
17	Correct	6 ms	5112 KB	Output is correct
18	Runtime error	23 ms	13176 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Halted	0 ms	0 KB	-

답안 #169258

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 12.0

Subtask #3 0 / 24.0

Subtask #4 0 / 27.0

Subtask #5 0 / 26.0

Subtask #1
11.0 / 11.0

Subtask #2
0 / 12.0

Subtask #3
0 / 24.0

Subtask #4
0 / 27.0

Subtask #5
0 / 26.0