Submission #548645

#	Time	Username	Problem	Language	Result	Execution time	Memory
548645		Khizri	Fountain Parks (IOI21_parks)	C++17	15 / 100	519 ms	59852 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
const int mxn=2e5+5;
int color[mxn],say;
map<pii,int>mp;
map<int,bool>l,r;
vector<int>vt[mxn];
void dfs(int u){
    color[u]=1;
    say++;
    for(int v:vt[u]){
        if(!color[v]){
            dfs(v);
        }
    }
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    vector<int>a,b;
    for(int i=0;i<x.size();i++){
        mp[{x[i],y[i]}]=i;
        if(x[i]==2){
            a.pb(y[i]);
            l[y[i]]=1;
        }
        else{
            b.pb(y[i]);
            r[y[i]]=1;
        }
    }
    sort(all(a));
    sort(all(b));
    vector<int>u,v,ax,bx;
    for(int i=1;i<a.size();i++){
        if(a[i]-a[i-1]==2){
            u.pb(mp[{2,a[i-1]}]);
            v.pb(mp[{2,a[i]}]);
            vt[u.back()].pb(v.back());
            vt[v.back()].pb(u.back());
            ax.pb(1);
            bx.pb((a[i]+a[i-1])/2);
        }
    }
    for(int i=1;i<b.size();i++){
        if(b[i]-b[i-1]==2){
            u.pb(mp[{4,b[i-1]}]);
            v.pb(mp[{4,b[i]}]);
            vt[u.back()].pb(v.back());
            vt[v.back()].pb(u.back());
            ax.pb(5);
            bx.pb((b[i]+b[i-1])/2);
        }
    }
    for(int i=2;i<=200000;i+=2){
        if(l[i]&&r[i]){
            u.pb(mp[{2,i}]);
            v.pb(mp[{4,i}]);
            vt[u.back()].pb(v.back());
            vt[v.back()].pb(u.back());
            ax.pb(3);
            bx.pb(i-1);
        }
    }
    dfs(0);
    if(say!=x.size()){
        return 0;
    }
    build(u,v,ax,bx);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~
parks.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=1;i<a.size();i++){
      |                 ~^~~~~~~~~
parks.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=1;i<b.size();i++){
      |                 ~^~~~~~~~~
parks.cpp:74:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     if(say!=x.size()){
      |        ~~~^~~~~~~~~~

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