Submission #94968

#TimeUsernameProblemLanguageResultExecution timeMemory
94968Retro3014Flood (IOI07_flood)C++17
42 / 100
103 ms9620 KiB
#include <iostream> #include <algorithm> #include <vector> #include <deque> #include <stdio.h> using namespace std; #define MAX_N 100000 int N, W; struct P{ int x, y; int c[4][2]; }; vector<P> point; struct S{ int x, y; int type; }; vector<S> line; vector<int> idx; bool ans1[MAX_N*2+1], ans2[MAX_N*2+1]; void rotate(int x, int y){ //printf("0\n"); while(1){ //printf("%d %d\n", point[x].x, point[x].y); for(int i=1; i<=4; i++){ if(point[x].c[(y+i)%4][0]!=-1){ if(point[x].c[(y+i)%4][1]==-1){ while(!idx.empty()){ S now = line[idx.back()]; idx.pop_back(); if(now.type==1){ point[now.x].c[0][0] = -1; point[now.y].c[2][0] = -1; }else{ point[now.x].c[1][0] = -1; point[now.y].c[3][0] = -1; } } return; } int xx = x, yy = y; y = (y+i+2)%4; x = point[x].c[(yy+i)%4][0]; if(ans1[point[xx].c[(yy+i)%4][1]]){ ans1[point[xx].c[(yy+i)%4][1]]=false; idx.push_back(point[xx].c[(yy+i)%4][1]); }else{ ans2[point[xx].c[(yy+i)%4][1]]=true; } point[xx].c[(yy+i)%4][1] = -1; break; } } } } struct S2{ int idx, data; bool operator <(const S2 &a)const{ return data<a.data; } }; vector<S2> v2; int main(){ scanf("%d", &N); P sc; for(int i=0; i<4; i++){ for(int j=0; j<2; j++){ sc.c[i][j] = -1; } } for(int i=0; i<N; i++){ scanf("%d%d", &sc.x, &sc.y); point.push_back(sc); } scanf("%d", &W); for(int i=0; i<W; i++){ ans1[i] = true; } int a, b; for(int i=0; i<W; i++){ scanf("%d%d", &a, &b); a--; b--; if(point[a].x==point[b].x){ if(point[a].y>point[b].y) {int t = a; a = b; b = t;} point[a].c[0][0] = b; point[a].c[0][1] = line.size(); point[b].c[2][0] = a; point[b].c[2][1] = line.size(); v2.push_back({line.size(), point[a].x}); line.push_back({a, b, 1}); }else{ if(point[a].x>point[b].x) {int t = a; a = b; b = t;} point[a].c[1][0] = b; point[a].c[1][1] = line.size(); point[b].c[3][0] = a; point[b].c[3][1] = line.size(); line.push_back({a, b, 2}); } } sort(v2.begin(), v2.end()); for(int i=0; i<v2.size(); i++){ if(!ans1[v2[i].idx]) continue; S now = line[v2[i].idx]; rotate(now.y, 2); } int ans = 0; for(int i=0; i<W; i++){ ans+=(ans2[i]); } printf("%d\n", ans); for(int i=0; i<W; i++){ if(ans2[i]){ printf("%d\n", i+1); } } return 0; }

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:91:27: warning: narrowing conversion of 'line.std::vector<S>::size()' from 'std::vector<S>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
    v2.push_back({line.size(), point[a].x});
                  ~~~~~~~~~^~
flood.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v2.size(); i++){
               ~^~~~~~~~~~
flood.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
flood.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &sc.x, &sc.y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
flood.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &W);
  ~~~~~^~~~~~~~~~
flood.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
#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...