Submission #987352

#	Time	Username	Problem	Language	Result	Execution time	Memory
987352		huutuan	Flood (IOI07_flood)	C++14	100 / 100	88 ms	19408 KiB

flood

#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 / 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