oj.uz

Submission #987352

# Submission time Handle Problem Language Result Execution time Memory
987352 2024-05-22T15:54:14 Z huutuan Flood (IOI07_flood) C++14
100 / 100
 88 ms 19408 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=2e5+10, dx[]={0, -1, 0, 1}, dy[]={-1, 0, 1, 0};
int n, m;
pair<int, int> pos[N], edge[N];
pair<int, int> g[N][4];
int id[N], vis[N], dir[N];

int sgn(int x){ return (x>0)-(x<0); }

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i){
      cin >> pos[i].first >> pos[i].second;
      for (int j=0; j<4; ++j) g[i][j]={-1, -1};
   }
   cin >> m;
   for (int i=1; i<=m; ++i){
      int u, v; cin >> u >> v;
      edge[i]={u, v};
      for (int j=0; j<4; ++j) if (sgn(pos[v].first-pos[u].first)==dx[j] && sgn(pos[v].second-pos[u].second)==dy[j]){
         g[u][j]={v, i};
         g[v][j^2]={u, i};
         dir[i]=j;
      }
   }
   iota(id, id+n+1, 0);
   sort(id+1, id+n+1, [&](int x, int y){ return pos[x]>pos[y]; });
   for (int ii=1; ii<=n; ++ii){
      int i=id[ii];
      int u=i, d=-1;
      for (int j=0; j<4; ++j) if (g[i][j].first!=-1){
         d=j;
         break;
      }
      if (d==-1) continue;
      pair<int, int> tmp={u, d};
      vector<int> vv;
      do{
         int v=g[u][d].first, eid=g[u][d].second;
         vv.push_back(eid);
         vis[eid]^=1;
         u=v;
         d=(d+3)%4;
         while (g[u][d].first==-1) d=(d+1)%4;
      }while (tmp!=make_pair(u, d));
      for (int j:vv){
         g[edge[j].first][dir[j]]={-1, -1};
         g[edge[j].second][dir[j]^2]={-1, -1};
      }
   }
   cout << m-accumulate(vis+1, vis+m+1, 0) << '\n';
   for (int i=1; i<=m; ++i) if (!vis[i]) cout << i << '\n';
   return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10668 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11612 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16596 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16276 KB Output is correct
2 Correct 80 ms 18952 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 18284 KB Output is correct
2 Correct 69 ms 19092 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 18900 KB Output is correct
2 Correct 54 ms 19408 KB Output is correct