Submission #66759

#TimeUsernameProblemLanguageResultExecution timeMemory
66759cdemirerDango Maker (JOI18_dango_maker)C++17
13 / 100
216 ms212180 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<vi> vvi; typedef pair<double, double> dodo; #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) int N, M; vvi edges; int num_nodes = 0; int createNode() { edges.pb(vi()); return num_nodes++; } void connect(int a, int b) { edges[a].pb(b); edges[b].pb(a); } const int ARRSIZE = 3000*3000; int parent[ARRSIZE]; bool vis[ARRSIZE] = {0}; /*int dpi[ARRSIZE], dpe[ARRSIZE]; void dfs(int x) { vis[x] = true; int no = -1; for (int i = 0; i < edges[x].size(); i++) { int y = edges[x][i]; if (y == parent[x]) continue; if (vis[y]) { no = i; continue; } parent[y] = x; dfs(y); } dpi[x] = 1; for (int i = 0; i < edges[x].size(); i++) { int y = edges[x][i]; if (y == parent[x]) continue; if (y == no) continue; dpi[x] += dpe[y]; } dpe[x] = 0; for (int i = 0; i < edges[x].size(); i++) { int y = edges[x][i]; if (y == parent[x]) continue; if (y == no) continue; dpe[x] += max(dpi[y], dpe[y]); } }*/ int bfs(int x, bool b) { int ret = 0; queue<ii> Q; Q.push(mp(x, (int)b)); while (!Q.empty()) { ii a = Q.front(); Q.pop(); if (vis[a.first]) continue; vis[a.first] = true; ret += a.second; for (int i = 0; i < edges[a.first].size(); i++) { int y = edges[a.first][i]; Q.push(mp(y, !a.second)); } } return ret; } void clean(int x) { vis[x] = false; for (int i = 0; i < edges[x].size(); i++) { int y = edges[x][i]; if (!vis[y]) continue; clean(y); } } int mat[3000][3000]; vi touch[3000][3000]; void memory_opt() { cin >> N >> M; for (int i = 0; i < N; i++) { string s; cin >> s; for (int j = 0; j < M; j++) { if (s[j] == 'R') mat[i][j] = 0; if (s[j] == 'G') mat[i][j] = 1; if (s[j] == 'W') mat[i][j] = 2; } } for (int i = 0; i < N; i++) { for (int j = 0; j < M-2; j++) { if (mat[i][j]*9 + mat[i][j+1]*3 + mat[i][j+2]*1 == 5) { int x = createNode(); if (touch[i][j].size() > 0) { for (int k = 0; k < touch[i][j].size(); k++) connect(x, touch[i][j][k]); } touch[i][j].pb(x); if (touch[i][j+1].size() > 0) { for (int k = 0; k < touch[i][j+1].size(); k++) connect(x, touch[i][j+1][k]); } touch[i][j+1].pb(x); if (touch[i][j+2].size() > 0) { for (int k = 0; k < touch[i][j+2].size(); k++) connect(x, touch[i][j+2][k]); } touch[i][j+2].pb(x); } } } for (int i = 0; i < N-2; i++) { for (int j = 0; j < M; j++) { if (mat[i][j]*9 + mat[i+1][j]*3 + mat[i+2][j]*1 == 5) { int x = createNode(); if (touch[i][j].size() > 0) { for (int k = 0; k < touch[i][j].size(); k++) connect(x, touch[i][j][k]); } touch[i][j].pb(x); if (touch[i+1][j].size() > 0) { for (int k = 0; k < touch[i+1][j].size(); k++) connect(x, touch[i+1][j][k]); } touch[i+1][j].pb(x); if (touch[i+2][j].size() > 0) { for (int k = 0; k < touch[i+2][j].size(); k++) connect(x, touch[i+2][j][k]); } touch[i+2][j].pb(x); } } } } int main(int argc, char **argv) { ios_base::sync_with_stdio(0); cin.tie(0); memory_opt(); //cerr << num_nodes << endl; int sum = 0; for (int i = 0; i < num_nodes; i++) { if (vis[i]) continue; //parent[i] = -1; int a = bfs(i, true); clean(i); int b = bfs(i, false); sum += max(a, b); //sum += max(dpi[i], dpe[i]); //cerr << "i am " << i << " i added " << max(dpi[i], dpe[i]) << endl; } cout << sum << endl; return 0; }

Compilation message (stderr)

dango_maker.cpp: In function 'int bfs(int, bool)':
dango_maker.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[a.first].size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp: In function 'void clean(int)':
dango_maker.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges[x].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
dango_maker.cpp: In function 'void memory_opt()':
dango_maker.cpp:103:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < touch[i][j].size(); k++) connect(x, touch[i][j][k]);
                      ~~^~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:107:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < touch[i][j+1].size(); k++) connect(x, touch[i][j+1][k]);
                      ~~^~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:111:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < touch[i][j+2].size(); k++) connect(x, touch[i][j+2][k]);
                      ~~^~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:122:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < touch[i][j].size(); k++) connect(x, touch[i][j][k]);
                      ~~^~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:126:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < touch[i+1][j].size(); k++) connect(x, touch[i+1][j][k]);
                      ~~^~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:130:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int k = 0; k < touch[i+2][j].size(); k++) connect(x, touch[i+2][j][k]);
                      ~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...