Submission #603078

#	Time	Username	Problem	Language	Result	Execution time	Memory
603078		FatihSolak	Fountain Parks (IOI21_parks)	C++17	55 / 100	1262 ms	137416 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;
    vector<pair<int,int>> ord;
    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}])){
                    ord.push_back({i,mp[{x[i]+dx,y[i]+dy}]});
                    //u.push_back(i);
                    //v.push_back(mp[{x[i]+dx,y[i]+dy}]);
                }
            }
        }
    }
    sort(ord.begin(),ord.end(),[&](pair<int,int> c,pair<int,int> d){
        if(max(x[c.first],x[c.second]) != max(x[d.first],x[d.second])){
            return max(x[c.first],x[c.second]) < max(x[d.first],x[d.second]);
        }
        return max(y[c.first],y[c.second]) < max(y[d.first],y[d.second]);
    });
    for(auto c:ord){
        u.push_back(c.first);
        v.push_back(c.second);
    }
    if(u.size() != n-1)
        return 0;
    a.assign(n-1,-1);
    b.assign(n-1,-1);
    map<pair<int,int>,int> used;
    map<int,int> cnt;
    map<pair<int,int>,vector<int>> mpp;
    set<pair<int,int>> s;
    for(int i = 0;i<n-1;i++){
        for(auto dx:{-1,1}){
            for(auto dy:{-1,1}){   
                if(abs(x[u[i]]+dx - x[v[i]]) != 1 || abs(y[u[i]]+dy - y[v[i]]) != 1)continue;
                cnt[i]++;
                mpp[{x[u[i]]+dx,y[u[i]]+dy}].push_back(i);
            }
        }
        s.insert({cnt[i],i});
    }
    while(s.size()){
        auto tp = *s.begin();
        if(tp.first == 0){
            assert(0);
        }
        s.erase(tp);
        int i = tp.second;
        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[i] = x[u[i]] + dx;
                b[i] = y[u[i]] + dy;
                for(auto z:mpp[{x[u[i]]+dx,y[u[i]]+dy}]){
                    if(a[z] != -1)continue;
                    s.erase({cnt[z],z});
                    cnt[z]--;
                    s.insert({cnt[z],z});
                }
                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:54:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     if(u.size() != n-1)
      |        ~~~~~~~~~^~~~~~

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