oj.uz

Submission #172654

# Submission time Handle Problem Language Result Execution time Memory
172654 2020-01-02T09:41:00 Z AlexLuchianov Flood (IOI07_flood) C++14
100 / 100
 397 ms 18536 KB 
#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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 19 ms 5112 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5156 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7012 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 11892 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 12080 KB Output is correct
2 Correct 374 ms 17204 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 15880 KB Output is correct
2 Correct 397 ms 18536 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 17172 KB Output is correct
2 Correct 271 ms 12940 KB Output is correct