Hämähäkit

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;

#define F first
#define S second

using namespace std;

vector<pair<ld,ll>> gr[101010];
pair<ll,ll> loc[101010];
int used[101010];
int used2[101010];
int w;
int par[101010];

int dfs(int x) {
  for (int i=0;i<101010;i++) used[i]=0;
  priority_queue<pair<ld,int>> pq;
  pq.push({0,x});
  vector<int> vis;
  while (!pq.empty()) {
    auto y=pq.top();
    pq.pop();
    if (used[y.S] || used2[y.S]) continue;
    used[y.S]=1;
    vis.push_back(y.S);
    if (loc[y.S].F==w) {
      int hlp=y.S;
      while (hlp!=x) {
	used2[hlp]=1;
	hlp=par[hlp];
      }
      used2[x]=1;
      return 1;
    }
    for (auto z : gr[y.S]) {
      if (!used[z.S]) {
	pq.push({z.F,z.S});
	par[z.S]=y.S;
      }
    }
  }
  for (auto r : vis) used2[r]=1;
  return 0;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin>>n>>m>>w;
  vector<pair<int,int>> beg;
  for (int i=1;i<=n;i++) {
    int x,y;
    cin>>x>>y;
    loc[i]={x,y};
    if (x==0) beg.push_back({-y,i});
  }
  sort(beg.begin(),beg.end());
  for (int i=0;i<m;i++) {
    int a,b;
    cin>>a>>b;
    ld hlp=sqrt((loc[a].F-loc[b].F)*(loc[a].F-loc[b].F)+(loc[a].S-loc[b].S)*(loc[a].S-loc[b].S));
    gr[a].push_back({(loc[b].S-loc[a].S)/hlp,b});
    gr[b].push_back({(loc[a].S-loc[b].S)/hlp,a});
  }
  int res=0;
  for (auto x : beg) {
    res+=dfs(x.S);
  }
  cout<<res<<"\n";
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 1

Verdict: ACCEPTED

Test 19

Group: 1

Verdict: ACCEPTED

Test 20

Group: 1

Verdict: ACCEPTED

Test 21

Group: 1

Verdict: ACCEPTED

Test 22

Group: 1

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: WRONG ANSWER

Test 24

Group: 2

Verdict: WRONG ANSWER

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: WRONG ANSWER

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: WRONG ANSWER

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: WRONG ANSWER

Test 32

Group: 2

Verdict: ACCEPTED

Test 33

Group: 2

Verdict: ACCEPTED

Test 34

Group: 2

Verdict: WRONG ANSWER

Test 35

Group: 2

Verdict: WRONG ANSWER

Test 36

Group: 2

Verdict: ACCEPTED

Test 37

Group: 2

Verdict: WRONG ANSWER

Test 38

Group: 2

Verdict: ACCEPTED

Test 39

Group: 2

Verdict: ACCEPTED

Test 40

Group: 2

Verdict: ACCEPTED

Test 41

Group: 2

Verdict: ACCEPTED

Test 42

Group: 2

Verdict: ACCEPTED

Test 43

Group: 2

Verdict: ACCEPTED

Test 44

Group: 2

Verdict: ACCEPTED

Test 45

Group: 3

Verdict: WRONG ANSWER

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: WRONG ANSWER

Test 48

Group: 3

Verdict: WRONG ANSWER

Test 49

Group: 3

Verdict: WRONG ANSWER

Test 50

Group: 3

Verdict: WRONG ANSWER

Test 51

Group: 3

Verdict: WRONG ANSWER

Test 52

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 53

Group: 3

Verdict: WRONG ANSWER

Test 54

Group: 3

Verdict: ACCEPTED

Test 55

Group: 3

Verdict: WRONG ANSWER

Test 56

Group: 3

Verdict: ACCEPTED

Test 57

Group: 3

Verdict: WRONG ANSWER

Test 58

Group: 3

Verdict: WRONG ANSWER

Test 59

Group: 3

Verdict: WRONG ANSWER

Test 60

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 61

Group: 3

Verdict: ACCEPTED

Test 62

Group: 3

Verdict: ACCEPTED

Test 63

Group: 3

Verdict: WRONG ANSWER

Test 64

Group: 3

Verdict: WRONG ANSWER

Test 65

Group: 3

Verdict: ACCEPTED

Test 66

Group: 3

Verdict: TIME LIMIT EXCEEDED