Submission #95308

#TimeUsernameProblemLanguageResultExecution timeMemory
95308ics0503Flood (IOI07_flood)C++17
40 / 100
157 ms33792 KiB
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; struct xy { int x, y, w; }a[121212]; bool sort_x(xy a, xy b) { if (a.x != b.x)return a.x < b.x; return a.y < b.y; } bool sort_y(xy a, xy b) { if (a.y != b.y)return a.y < b.y; return a.x < b.x; } vector<xy>edge[828282]; vector<int>Q[2]; int ck[121212][4], is_ans[121212], dist[828282]; void swap(int &a, int &b) { a ^= b ^= a ^= b; } void addE(int s, int e, int w, int i) { edge[s].push_back({ e, w , i}); edge[e].push_back({ s, w , i}); } int main() { int P, L, i, j; scanf("%d", &P); for (i = 1; i <= P; i++)scanf("%d%d", &a[i].x, &a[i].y), a[i].w = i; scanf("%d", &L); for (int i = 1; i <= L; i++) { int s, e; scanf("%d%d", &s, &e); if (a[s].y == a[e].y) { if (a[s].x > a[e].x)swap(s, e); ck[s][3] = i; ck[e][1] = i; } else { if (a[s].y > a[e].y)swap(s, e); ck[s][2] = i; ck[e][0] = i; } } sort(a + 1, a + P + 1, sort_x); for (int i = 1; i < P; i++) if (a[i].x == a[i + 1].x) addE(8 * a[i].w + 4, 8 * a[i + 1].w + 1, 0, 0), addE(8 * a[i].w + 5, 8 * a[i + 1].w + 0, 0, 0); sort(a + 1, a + P + 1, sort_y); for (int i = 1; i < P; i++) if (a[i].y == a[i + 1].y) addE(8 * a[i].w + 6, 8 * a[i + 1].w + 3, 0, 0), addE(8 * a[i].w + 7, 8 * a[i + 1].w + 2, 0, 0); int n = (P + 1) * 8 - 1; for (int i = 1; i <= P; i++) for (int j = 0; j < 4; j++) { addE(i * 8 + 2 * j, i * 8 + 2 * j + 1, !!ck[i][j], ck[i][j]); addE(i * 8 + 2 * j + 1, i * 8 + (2 * j + 2) % 8, 0, 0); } for (int i = 8; i <= n; i++) { if (dist[i]) continue; int dst; dst = dist[i] = 1; Q[1].push_back(i); while (!(Q[0].empty() && Q[1].empty())) { if (Q[dst % 2].empty()) { dst++; continue; } int now = Q[dst % 2].back(); Q[dst % 2].pop_back(); if (dist[now]%2 != dst % 2)continue; for (auto E : edge[now]) { if (dist[E.x] == 0 || dist[E.x] > dst + E.y) { dist[E.x] = dst + E.y; Q[(dst + E.y) % 2].push_back(E.x); } } } } for (int i = 8; i <= n; i++) for (auto E : edge[i]) if (dist[i] == dist[E.x]) is_ans[E.w] = 1; int ansCnt = 0; for (int i = 1; i <= L; i++) if (is_ans[i])ansCnt++; printf("%d\n", ansCnt); for (int i = 1; i <= L; i++) if (is_ans[i])printf("%d\n", i); return 0; }

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:17:15: warning: unused variable 'j' [-Wunused-variable]
  int P, L, i, j; scanf("%d", &P);
               ^
flood.cpp:17:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int P, L, i, j; scanf("%d", &P);
                  ~~~~~^~~~~~~~~~
flood.cpp:18:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= P; i++)scanf("%d%d", &a[i].x, &a[i].y), a[i].w = i;
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
flood.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &L);
  ~~~~~^~~~~~~~~~
flood.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d%d", &s, &e);
             ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...