답안 #48557 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48557	2018-05-16T09:40:17 Z	ngkan146	Dango Maker (JOI18_dango_maker)	C++11	13 / 100	5 ms	3300 KB

dango_maker

#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> iii;
int n,m;
string s[3005];
vector <int> G[100005];
bool visited[100005];
bool mark[2][3005][3005];   // 0 = down, 1 = right
int glob, cnt;
void dfs(int u, int color){
    visited[u] = 1;
    glob ++;
    cnt += (color == 0);
    for(auto v: G[u]){
        if (!visited[v])
            dfs(v, color ^= 1);
    }
}
int main(){
    iostream::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++)   cin >> s[i], s[i] = '0' + s[i];
    int ans = 0;
    vector <iii> lst;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if (i <= n-2 && s[i][j] == 'R' && s[i+1][j] == 'G' && s[i+2][j] == 'W')
                mark[0][i][j] = 1,
                lst.push_back(iii(0,i,j));
            if (j <= m-2 && s[i][j] == 'R' && s[i][j+1] == 'G' && s[i][j+2] == 'W')
                mark[1][i][j] = 1,
                lst.push_back(iii(1,i,j));
        }
    }
    sort(lst.begin(), lst.end());

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if (mark[0][i][j]){
                int id1 = lower_bound(lst.begin(), lst.end(), iii(0,i,j)) - lst.begin() + 1;
                int id2;
                if (mark[1][i][j]){
                    id2 = lower_bound(lst.begin(), lst.end(), iii(1,i,j)) - lst.begin() + 1;
                    G[id1].push_back(id2);
                }
                if (i < n && j > 1 && mark[1][i+1][j-1]){
                    id2 = lower_bound(lst.begin(), lst.end(), iii(1,i+1,j-1)) - lst.begin() + 1;
                    G[id1].push_back(id2);
                }
                if (i < n-1 && j > 2 && mark[1][i+2][j-2]){
                    id2 = lower_bound(lst.begin(), lst.end(), iii(1,i+2,j-2)) - lst.begin() + 1;
                    G[id1].push_back(id2);
                }
            }
            if (mark[1][i][j]){
                int id1 = lower_bound(lst.begin(), lst.end(), iii(1,i,j)) - lst.begin() + 1;
                int id2;
                if (mark[0][i][j]){
                    id2 = lower_bound(lst.begin(), lst.end(), iii(0,i,j)) - lst.begin() + 1;
                    G[id1].push_back(id2);
                }
                if (i > 1 && j < m && mark[0][i-1][j+1]){
                    id2 = lower_bound(lst.begin(), lst.end(), iii(0,i-1,j+1)) - lst.begin() + 1;
                    G[id1].push_back(id2);
                }
                if (i > 2 && j < m-1 && mark[0][i-2][j+2]){
                    id2 = lower_bound(lst.begin(), lst.end(), iii(0,i-2,j+2)) - lst.begin() + 1;
                    G[id1].push_back(id2);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if (mark[0][i][j]){
                int id = lower_bound(lst.begin(), lst.end(), iii(0,i,j)) - lst.begin() + 1;
                if (visited[id])    continue;
                glob = cnt = 0;
                dfs(id, 0);
                ans += max(cnt, glob-cnt);
            }
            if (mark[1][i][j]){
                int id = lower_bound(lst.begin(), lst.end(), iii(1,i,j)) - lst.begin() + 1;
                if (visited[id])    continue;
                glob = cnt = 0;
                dfs(id, 0);
                ans += max(cnt, glob-cnt);
            }
        }
    }
    cout << ans;
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	4 ms	2808 KB	Output is correct
3	Correct	4 ms	2860 KB	Output is correct
4	Correct	4 ms	2860 KB	Output is correct
5	Correct	4 ms	2912 KB	Output is correct
6	Correct	4 ms	3080 KB	Output is correct
7	Correct	4 ms	3080 KB	Output is correct
8	Correct	3 ms	3100 KB	Output is correct
9	Correct	4 ms	3100 KB	Output is correct
10	Correct	4 ms	3100 KB	Output is correct
11	Correct	3 ms	3100 KB	Output is correct
12	Correct	4 ms	3100 KB	Output is correct
13	Correct	4 ms	3100 KB	Output is correct
14	Correct	4 ms	3100 KB	Output is correct
15	Correct	4 ms	3100 KB	Output is correct
16	Correct	5 ms	3160 KB	Output is correct

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	4 ms	2808 KB	Output is correct
3	Correct	4 ms	2860 KB	Output is correct
4	Correct	4 ms	2860 KB	Output is correct
5	Correct	4 ms	2912 KB	Output is correct
6	Correct	4 ms	3080 KB	Output is correct
7	Correct	4 ms	3080 KB	Output is correct
8	Correct	3 ms	3100 KB	Output is correct
9	Correct	4 ms	3100 KB	Output is correct
10	Correct	4 ms	3100 KB	Output is correct
11	Correct	3 ms	3100 KB	Output is correct
12	Correct	4 ms	3100 KB	Output is correct
13	Correct	4 ms	3100 KB	Output is correct
14	Correct	4 ms	3100 KB	Output is correct
15	Correct	4 ms	3100 KB	Output is correct
16	Correct	5 ms	3160 KB	Output is correct
17	Correct	3 ms	3160 KB	Output is correct
18	Correct	4 ms	3160 KB	Output is correct
19	Correct	4 ms	3160 KB	Output is correct
20	Correct	4 ms	3160 KB	Output is correct
21	Correct	4 ms	3160 KB	Output is correct
22	Correct	4 ms	3160 KB	Output is correct
23	Correct	4 ms	3160 KB	Output is correct
24	Correct	4 ms	3160 KB	Output is correct
25	Correct	4 ms	3160 KB	Output is correct
26	Correct	4 ms	3160 KB	Output is correct
27	Correct	4 ms	3160 KB	Output is correct
28	Correct	4 ms	3160 KB	Output is correct
29	Correct	4 ms	3168 KB	Output is correct
30	Correct	4 ms	3168 KB	Output is correct
31	Correct	4 ms	3300 KB	Output is correct
32	Correct	4 ms	3300 KB	Output is correct
33	Incorrect	4 ms	3300 KB	Output isn't correct
34	Halted	0 ms	0 KB	-

Subtask #3
0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	4 ms	2808 KB	Output is correct
3	Correct	4 ms	2860 KB	Output is correct
4	Correct	4 ms	2860 KB	Output is correct
5	Correct	4 ms	2912 KB	Output is correct
6	Correct	4 ms	3080 KB	Output is correct
7	Correct	4 ms	3080 KB	Output is correct
8	Correct	3 ms	3100 KB	Output is correct
9	Correct	4 ms	3100 KB	Output is correct
10	Correct	4 ms	3100 KB	Output is correct
11	Correct	3 ms	3100 KB	Output is correct
12	Correct	4 ms	3100 KB	Output is correct
13	Correct	4 ms	3100 KB	Output is correct
14	Correct	4 ms	3100 KB	Output is correct
15	Correct	4 ms	3100 KB	Output is correct
16	Correct	5 ms	3160 KB	Output is correct
17	Correct	3 ms	3160 KB	Output is correct
18	Correct	4 ms	3160 KB	Output is correct
19	Correct	4 ms	3160 KB	Output is correct
20	Correct	4 ms	3160 KB	Output is correct
21	Correct	4 ms	3160 KB	Output is correct
22	Correct	4 ms	3160 KB	Output is correct
23	Correct	4 ms	3160 KB	Output is correct
24	Correct	4 ms	3160 KB	Output is correct
25	Correct	4 ms	3160 KB	Output is correct
26	Correct	4 ms	3160 KB	Output is correct
27	Correct	4 ms	3160 KB	Output is correct
28	Correct	4 ms	3160 KB	Output is correct
29	Correct	4 ms	3168 KB	Output is correct
30	Correct	4 ms	3168 KB	Output is correct
31	Correct	4 ms	3300 KB	Output is correct
32	Correct	4 ms	3300 KB	Output is correct
33	Incorrect	4 ms	3300 KB	Output isn't correct
34	Halted	0 ms	0 KB	-

답안 #48557

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 0 / 20.0

Subtask #3 0 / 67.0

Subtask #1
13.0 / 13.0

Subtask #2
0 / 20.0

Subtask #3
0 / 67.0