제출 #118701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
118701		nvmdava	Flood (IOI07_flood)	C++17	30 / 100	202 ms	45988 KiB

flood

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9