제출 #172654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172654		AlexLuchianov	Flood (IOI07_flood)	C++14	100 / 100	397 ms	18536 KiB

flood

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
struct Point{
  int x;
  int y;
} v[1 + nmax];

struct Edge{
  int to;
  int dir;
  int id;
};
vector<Edge> g[1 + nmax];
int seen[1 + nmax], alive[1 + nmax], active[1 + nmax];

struct Horizontal{
  int start;
  int x;
  int id;
  bool operator < (Horizontal const &a) const{
    return x < a.x;
  }
};

int trydir(int node, int dir){
  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    if(e.dir == dir && alive[e.id] == 1){
      return e.id;
    }
  }
  return 0;
}

int go_dir(int node, int dir){
  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    if(e.dir == dir && alive[e.id] == 1){
      return e.to;
    }
  }
  return node;
}

int main()
{
  int n, m;
  cin >> n;
  for(int i = 1;i <= n; i++)
    cin >> v[i].x >> v[i].y;
  cin >> m;

  vector<Horizontal> figure;
  for(int i = 1;i <= m; i++){
    int a, b;
    cin >> a >> b;
    if(v[a].x == v[b].x){
      if(v[a].y < v[b].y){
        g[a].push_back({b, 2, i});
        g[b].push_back({a, 0, i});
        figure.push_back({a, v[a].x, i});
      } else {
        g[a].push_back({b, 0, i});
        g[b].push_back({a, 2, i});
        figure.push_back({b, v[a].x, i});
      }
    } else {
      if(v[a].x < v[b].x){
        g[a].push_back({b, 1, i});
        g[b].push_back({a, 3, i});
      } else {
        g[a].push_back({b, 3, i});
        g[b].push_back({a, 1, i});
      }
    }
    alive[i] = 1;
  }

  sort(figure.begin(), figure.end());
  for(int i = 0; i < figure.size(); i++){
    if(alive[figure[i].id] == 1) {
      int start = figure[i].start;
      int dir = 1;
      int node = start;
      vector<int> path;
      do {
        for(int h = 1 ; -2 <= h; h--){
          int e = trydir(node, (dir + 4 + h) % 4);
          if(0 < e){
            node = go_dir(node, (dir + 4 + h) % 4);
            dir = (dir + 4 + h) % 4;
            path.push_back(e);
            seen[e]++;
            break;
          }
        }
      } while(start != node);
      for(int i = 0; i < path.size(); i++)
        alive[path[i]] = 0;
    }
  }

  vector<int> sol;
  for(int i = 1;i <= m; i++)
    if(seen[i] != 1)
      sol.push_back(i);
  cout << sol.size() << '\n';
  for(int i = 0; i < sol.size(); i++)
    cout << sol[i] << '\n' ;
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

flood.cpp: In function 'int trydir(int, int)':
flood.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
flood.cpp: In function 'int go_dir(int, int)':
flood.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
flood.cpp: In function 'int main()':
flood.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < figure.size(); i++){
                  ~~^~~~~~~~~~~~~~~
flood.cpp:107:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < path.size(); i++)
                      ~~^~~~~~~~~~~~~
flood.cpp:117:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sol.size(); i++)
                  ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9