Submission #603000

#	Time	Username	Problem	Language	Result	Execution time	Memory
603000		FatihSolak	Fountain Parks (IOI21_parks)	C++17	5 / 100	636 ms	38868 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int par[N];
int find(int a){
    if(a == par[a])return a;
    return par[a] = find(par[a]);
}
bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a == b)
        return 0;
    par[a] = b;
    return 1;
}
int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    int n = x.size();
    map<pair<int,int>,int> mp;
    for(int i = 0;i<n;i++){
        par[i] = i;
        mp[{x[i],y[i]}] = i;
    }
    vector<int> u, v, a, b;
    for(int i = 0;i<n;i++){
        for(auto dx:{-2,0,2}){
            for(auto dy:{-2,0,2}){
                if(abs(dx) + abs(dy) != 2)continue;
                if(!mp.count({x[i]+dx,y[i]+dy}))continue;
                if(merge(i,mp[{x[i]+dx,y[i]+dy}])){
                    u.push_back(i);
                    v.push_back(mp[{x[i]+dx,y[i]+dy}]);
                }
            }
        }
    }
    if(u.size() != n-1)
        return 0;
    map<pair<int,int>,int> used;
    for(int i = 0;i<n-1;i++){
        bool ok = 0;
        for(auto dx:{-1,1}){
            for(auto dy:{-1,1}){
                if(ok)continue;
                if(used.count({x[u[i]]+dx,y[u[i]]+dy}))continue;     
                if(abs(x[u[i]]+dx - x[v[i]]) != 1 || abs(y[u[i]]+dy - y[v[i]]) != 1)continue;
                used[{x[u[i]]+dx,y[u[i]]+dy}] = 1;
                a.push_back(x[u[i]] + dx);
                b.push_back(y[u[i]] + dy);
                ok = 1;
            }
        }
    }
    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:42:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |     if(u.size() != n-1)
      |        ~~~~~~~~~^~~~~~

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