Submission #436980

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
436980	2021-06-25 12:30:40	haojiandan	Fountain Parks (IOI21_parks)	C++17	100 / 100	951 ms	29040 KiB

parks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
const int maxn=(2e5)+10;
map<pair<int,int>,int> M;
int n,m,hd,tl;
bool vis[maxn];
int fx[4][2]={{-2,0},{2,0},{0,-2},{0,2}};
int q[maxn];
int construct_roads(vector<int> X,vector<int> Y) {
  n=(int)X.size();
  vector<int> u,v,a,b;
  
  for (int i=0;i<n;i++) M[MP(X[i],Y[i])]=i;
  hd=tl=1; q[1]=0; vis[0]=1;
  while (hd<=tl) {
    int x=X[q[hd]],y=Y[q[hd]]; hd++;
    for (int i=0;i<4;i++) {
      int xx=x+fx[i][0],yy=y+fx[i][1];
      if (M.count(MP(xx,yy))) {
        int id=M[MP(xx,yy)]; if (vis[id]) continue;
        vis[id]=1; q[++tl]=id;
      }
    }
  }
  if (tl!=n) return 0;
  
  for (int i=0;i<n;i++) {
    int x=X[i],y=Y[i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30