답안 #246164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246164	2020-07-08T10:17:57 Z	Nightlight	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	943 ms	262148 KB

dango_maker

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> adj[6000005];
char A[3005][3005];
int id[3001][3001];
int match[6000005];
bitset<6000005> vis;
int p;

void edge(int u, int v) {
//  cout << u << " " << v << "\n";
  adj[u].emplace_back(v);
  adj[v].emplace_back(u);
}

int kuhn(int u) {
  if(vis[u]) return 0;
  vis[u] = 1;
  for(int v : adj[u]) {
    if(match[v] == 0 || kuhn(match[v])) {
      match[u] = v;
      match[v] = u;
      return 1;
    }
  }
  return 0;
}

int main() {
  scanf("%d %d", &N, &M);
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) {
      scanf(" %c", &A[i][j]);
    }
  }
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) {
      if(A[i][j] == 'G') {
        if(A[i - 1][j] == 'R' && A[i + 1][j] == 'W') {
          id[i - 1][j] = ++p;
          id[i][j] = p;
          id[i + 1][j] = p;
        }
      }
    }
  }
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) {
      if(A[i][j] == 'R' && A[i][j + 1] == 'G' && A[i][j + 2] == 'W') {
        ++p;
        if(id[i][j]) edge(id[i][j], p);
        if(id[i][j + 1]) edge(id[i][j + 1], p);
        if(id[i][j + 2]) edge(id[i][j + 2], p);
      }
    }
  }
  bool ok = 0;
  int cnt = 0;
  while(ok == 0) {
    ok = 1;
    vis = 0;
    for(int i = 1; i <= p; i++) {
      if(match[i] == 0 && kuhn(i)) {
        cnt++;
        ok = 0;
      }
    }
  }
  printf("%d\n", p - cnt);
//  cin >> N;
}

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);
   ~~~~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:35:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf(" %c", &A[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	141944 KB	Output is correct
2	Correct	87 ms	142004 KB	Output is correct
3	Correct	86 ms	141944 KB	Output is correct
4	Correct	85 ms	141944 KB	Output is correct
5	Correct	83 ms	141944 KB	Output is correct
6	Correct	96 ms	141944 KB	Output is correct
7	Correct	85 ms	141944 KB	Output is correct
8	Correct	87 ms	141944 KB	Output is correct
9	Correct	87 ms	141944 KB	Output is correct
10	Correct	84 ms	141944 KB	Output is correct
11	Correct	88 ms	142072 KB	Output is correct
12	Correct	84 ms	141944 KB	Output is correct
13	Correct	87 ms	141944 KB	Output is correct
14	Correct	88 ms	141944 KB	Output is correct
15	Correct	88 ms	141944 KB	Output is correct
16	Correct	84 ms	142072 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	141944 KB	Output is correct
2	Correct	87 ms	142004 KB	Output is correct
3	Correct	86 ms	141944 KB	Output is correct
4	Correct	85 ms	141944 KB	Output is correct
5	Correct	83 ms	141944 KB	Output is correct
6	Correct	96 ms	141944 KB	Output is correct
7	Correct	85 ms	141944 KB	Output is correct
8	Correct	87 ms	141944 KB	Output is correct
9	Correct	87 ms	141944 KB	Output is correct
10	Correct	84 ms	141944 KB	Output is correct
11	Correct	88 ms	142072 KB	Output is correct
12	Correct	84 ms	141944 KB	Output is correct
13	Correct	87 ms	141944 KB	Output is correct
14	Correct	88 ms	141944 KB	Output is correct
15	Correct	88 ms	141944 KB	Output is correct
16	Correct	84 ms	142072 KB	Output is correct
17	Correct	84 ms	142112 KB	Output is correct
18	Correct	86 ms	142040 KB	Output is correct
19	Correct	87 ms	142072 KB	Output is correct
20	Correct	88 ms	142176 KB	Output is correct
21	Correct	89 ms	142072 KB	Output is correct
22	Correct	86 ms	142072 KB	Output is correct
23	Correct	86 ms	142072 KB	Output is correct
24	Correct	85 ms	142044 KB	Output is correct
25	Correct	89 ms	142072 KB	Output is correct
26	Correct	84 ms	141944 KB	Output is correct
27	Correct	83 ms	142072 KB	Output is correct
28	Correct	85 ms	142072 KB	Output is correct
29	Correct	85 ms	142072 KB	Output is correct
30	Correct	91 ms	142076 KB	Output is correct
31	Correct	90 ms	142016 KB	Output is correct
32	Correct	88 ms	142072 KB	Output is correct
33	Correct	84 ms	142072 KB	Output is correct
34	Correct	85 ms	142072 KB	Output is correct
35	Correct	87 ms	142072 KB	Output is correct
36	Correct	86 ms	142072 KB	Output is correct
37	Correct	85 ms	142072 KB	Output is correct
38	Correct	84 ms	142072 KB	Output is correct
39	Correct	82 ms	142072 KB	Output is correct
40	Correct	86 ms	142084 KB	Output is correct
41	Correct	85 ms	142072 KB	Output is correct
42	Correct	84 ms	142072 KB	Output is correct
43	Correct	90 ms	142072 KB	Output is correct
44	Correct	92 ms	142072 KB	Output is correct
45	Correct	88 ms	142248 KB	Output is correct
46	Correct	87 ms	142076 KB	Output is correct
47	Correct	85 ms	142072 KB	Output is correct
48	Correct	84 ms	142072 KB	Output is correct
49	Correct	82 ms	142040 KB	Output is correct
50	Correct	87 ms	142072 KB	Output is correct
51	Correct	90 ms	142076 KB	Output is correct
52	Correct	85 ms	142072 KB	Output is correct
53	Correct	85 ms	142072 KB	Output is correct

Subtask #3
0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	141944 KB	Output is correct
2	Correct	87 ms	142004 KB	Output is correct
3	Correct	86 ms	141944 KB	Output is correct
4	Correct	85 ms	141944 KB	Output is correct
5	Correct	83 ms	141944 KB	Output is correct
6	Correct	96 ms	141944 KB	Output is correct
7	Correct	85 ms	141944 KB	Output is correct
8	Correct	87 ms	141944 KB	Output is correct
9	Correct	87 ms	141944 KB	Output is correct
10	Correct	84 ms	141944 KB	Output is correct
11	Correct	88 ms	142072 KB	Output is correct
12	Correct	84 ms	141944 KB	Output is correct
13	Correct	87 ms	141944 KB	Output is correct
14	Correct	88 ms	141944 KB	Output is correct
15	Correct	88 ms	141944 KB	Output is correct
16	Correct	84 ms	142072 KB	Output is correct
17	Correct	84 ms	142112 KB	Output is correct
18	Correct	86 ms	142040 KB	Output is correct
19	Correct	87 ms	142072 KB	Output is correct
20	Correct	88 ms	142176 KB	Output is correct
21	Correct	89 ms	142072 KB	Output is correct
22	Correct	86 ms	142072 KB	Output is correct
23	Correct	86 ms	142072 KB	Output is correct
24	Correct	85 ms	142044 KB	Output is correct
25	Correct	89 ms	142072 KB	Output is correct
26	Correct	84 ms	141944 KB	Output is correct
27	Correct	83 ms	142072 KB	Output is correct
28	Correct	85 ms	142072 KB	Output is correct
29	Correct	85 ms	142072 KB	Output is correct
30	Correct	91 ms	142076 KB	Output is correct
31	Correct	90 ms	142016 KB	Output is correct
32	Correct	88 ms	142072 KB	Output is correct
33	Correct	84 ms	142072 KB	Output is correct
34	Correct	85 ms	142072 KB	Output is correct
35	Correct	87 ms	142072 KB	Output is correct
36	Correct	86 ms	142072 KB	Output is correct
37	Correct	85 ms	142072 KB	Output is correct
38	Correct	84 ms	142072 KB	Output is correct
39	Correct	82 ms	142072 KB	Output is correct
40	Correct	86 ms	142084 KB	Output is correct
41	Correct	85 ms	142072 KB	Output is correct
42	Correct	84 ms	142072 KB	Output is correct
43	Correct	90 ms	142072 KB	Output is correct
44	Correct	92 ms	142072 KB	Output is correct
45	Correct	88 ms	142248 KB	Output is correct
46	Correct	87 ms	142076 KB	Output is correct
47	Correct	85 ms	142072 KB	Output is correct
48	Correct	84 ms	142072 KB	Output is correct
49	Correct	82 ms	142040 KB	Output is correct
50	Correct	87 ms	142072 KB	Output is correct
51	Correct	90 ms	142076 KB	Output is correct
52	Correct	85 ms	142072 KB	Output is correct
53	Correct	85 ms	142072 KB	Output is correct
54	Correct	87 ms	142016 KB	Output is correct
55	Correct	92 ms	152056 KB	Output is correct
56	Correct	87 ms	142072 KB	Output is correct
57	Correct	105 ms	155512 KB	Output is correct
58	Correct	174 ms	153848 KB	Output is correct
59	Correct	811 ms	195108 KB	Output is correct
60	Correct	786 ms	195496 KB	Output is correct
61	Correct	797 ms	195192 KB	Output is correct
62	Correct	119 ms	141944 KB	Output is correct
63	Correct	763 ms	194900 KB	Output is correct
64	Runtime error	943 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
65	Halted	0 ms	0 KB	-

답안 #246164

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 67.0

Subtask #1
13.0 / 13.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 67.0