Submission #1051859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051859		MarwenElarbi	Fountain Parks (IOI21_parks)	C++17	5 / 100	317 ms	46620 KiB

parks

#include <bits/stdc++.h>
using namespace std;
#include "parks.h"
#define pb push_back
#define fi first
#define se second
const int nax=2e5+5;
set<pair<int,int>> mp;
map<pair<int,int>,int> cor;
set<pair<int,int>> vis;
bool check(pair<int,int> a){
    if(!mp.count({a.fi-2,a.se})&&!mp.count({a.fi+2,a.se})&&!mp.count({a.fi,a.se-2})&&!mp.count({a.fi,a.se+2})) return false;
    return true; 
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    std::vector<int> u, v, a, b;
    int n=y.size();
    for (int i = 0; i < n; ++i)
    {
        mp.insert({x[i],y[i]});
        cor[{x[i],y[i]}]=i;
    }
    bool test=true;
    for(auto i:mp){
        if(!check(i)){
            test=false;
            break;
        }
        if(mp.count({i.fi+2,i.se})){
            pair<int,int> cur={i.fi+1,i.se-1};
            if(vis.count(cur)) cur.se+=2;
            vis.insert(cur);
            a.pb(cur.fi);
            b.pb(cur.se);
            u.pb(cor[i]);
            v.pb(cor[{i.fi+2,i.se}]);
        }
        if(mp.count({i.fi,i.se+2})){
            pair<int,int> cur={i.fi-1,i.se+1};
            if(vis.count(cur)) cur.fi+=2;
            vis.insert(cur);
            a.pb(cur.fi);
            b.pb(cur.se);
            u.pb(cor[i]);
            v.pb(cor[{i.fi,i.se+2}]);
        }
    }
    if(!test) return 0;
    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:53:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     if(u.size()!=n-1) return 0;
      |        ~~~~~~~~^~~~~

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