Submission #1060844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060844		boyliguanhan	Fountain Parks (IOI21_parks)	C++17	100 / 100	294 ms	60352 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
map<int,int> pts[200100];
vector<pair<int,int>> tre_edges;
struct dsu{
    int par[200100];
    int abp(int n){
        return par[n]?par[n]=abp(par[n]):n;
    }
    int  merge(int a,int b){
        a=abp(a),b=abp(b);
        return a-b?par[a]=b:0;
    }
} DT;
int Xpos[400100],Ypos[400100];
int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n=x.size();
    for(int i=0;i<n;i++)
        pts[x[i]][y[i]]=i+1;
    vector<tuple<int,int,int>>pt;
    vector<array<int,4>> E;
    for(int i=0;i<n;i++)
        pt.push_back({x[i],y[i],i});
    sort(pt.begin(),pt.end());
    for(auto[X,Y,i]:pt) {
        int k=(X+Y>>1) % 2 ? 1 : -1;
        if(pts[X-2][Y])
            E.push_back({i+1,pts[X-2][Y],X-1,Y+k});
        if(pts[X][Y-2])
            E.push_back({i+1,pts[X][Y-2],X-k,Y-1});
    }
    vector<int>u,v,A,B;
    int CC=0;
    for(auto [i,j,x,y]:E){
        if(!pts[x][y]&&DT.merge(i,j)){
            u.push_back(i-1);
            v.push_back(j-1);
            A.push_back(x);
            B.push_back(y);
            pts[x][y]=1;
        }
    }
    if(u.size()-n+1)return 0;
    build(u,v,A,B);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:27:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int k=(X+Y>>1) % 2 ? 1 : -1;
      |                ~^~
parks.cpp:34:9: warning: unused variable 'CC' [-Wunused-variable]
   34 |     int CC=0;
      |         ^~

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