oj.uz

Submission #118701

# Submission time Handle Problem Language Result Execution time Memory
118701 2019-06-19T12:31:49 Z nvmdava Flood (IOI07_flood) C++17
30 / 100
 202 ms 45988 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

vector<pair<pair<int, int> , int>> dot;
set<int> adj[100005];
vector<pair<int, int> > wall;
int x[100005];
int y[100005];
set<int> ans;
set<int> in;
int cntr = 0;
void putout(int id){
   adj[wall[id].ff].erase(id);
   adj[wall[id].ss].erase(id);
}
void putin(int id){
   ans.insert(id);
   putout(id);
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   int n;
   cin>>n;
   for(int i = 0; i < n; i++){
      cin>>x[i]>>y[i];
      dot.push_back({{x[i], y[i]}, i});
   }
   int ww;
   cin>>ww;
   sort(dot.begin(), dot.end());

   for(int i = 0; i < ww; i++){
      int v, u;
      cin>>v>>u;
      v--;u--;
      adj[v].insert(i);
      adj[u].insert(i);
      wall.push_back({v, u});
   }
   for(auto p : dot){
      int st = p.ss;
      if(adj[st].empty()) continue;
      int v = p.ss;
      int to[4] = {-1, -1, -1, -1};
      for(int f : adj[v]){
         int u = wall[f].ss + wall[f].ff - v;
         if(x[v] == x[u]){
            if(y[u] > y[v]) to[0] = f;
            else to[2] = f;
         } else {
            if(x[u] > x[v]) to[1] = f;
            else to[3] = f;
         }
      }
      if(to[0] == -1){
         putin(to[1]);
         continue;
      }

      in.clear();
      in.insert(to[0]);
      v = wall[to[0]].ss + wall[to[0]].ff - v;
      int last = 0;

      while(v != st){
         memset(to, -1, sizeof to);
         for(int f : adj[v]){
            int u = wall[f].ss + wall[f].ff - v;
            if(x[v] == x[u]){
               if(y[u] > y[v]) to[0] = f;
               else to[2] = f;
            } else {
               if(x[u] > x[v]) to[1] = f;
               else to[3] = f;
            }
         }
         vector<int> que;
         if(last == 0){
            que = {3, 0, 1, 2};
         } else if(last == 1){
            que = {0, 1, 2, 3};
         } else if(last == 2){
            que = {1, 2, 3, 0};
         } else {
            que = {2, 3, 0, 1};
         }
         for(int x : que){
            if(to[x] != -1){
               if(in.count(to[x])){
                  in.erase(to[x]);
                  putin(to[x]);
               } else in.insert(to[x]);
               v = wall[to[x]].ff + wall[to[x]].ss - v;
               last = x;
               break;
            }
         }
      }
      for(int f : in)
         putout(f);
   }
   cout<<ans.size()<<'\n';
   for(int x : ans)
      cout<<x + 1<<'\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 15880 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 17268 KB Output isn't correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 18208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 163 ms 41596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 45988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -