Submission #436770

#	Time	Username	Problem	Language	Result	Execution time	Memory
436770		PiejanVDC	Fountain Parks (IOI21_parks)	C++17	15 / 100	304 ms	31124 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

int construct_roads(vector<int>x, vector<int> y) {
    vector<bool>used3(200005,false),used5(200005,false);
    vector<pair<int,int>>two,four,six;
    for(int i = 0 ; i < y.size() ; i++) {
        if(x[i] == 2) two.push_back({y[i],i});
        else if(x[i] == 4) four.push_back({y[i],i});
        else six.push_back({y[i],i});
    }
    vector<int>adj[x.size()];
    vector<int>u,v,a,b;
    sort(two.begin(),two.end());
    sort(four.begin(),four.end());
    sort(six.begin(),six.end());
    for(int i = 0 ; i < (int)two.size()-1 ; i++) {
        if(two[i+1].first-two[i].first == 2) {
            u.push_back(two[i].second);
            v.push_back(two[i+1].second);
            a.push_back(1);
            b.push_back(two[i].first+1);
            adj[two[i].second].push_back(two[i+1].second);
            adj[two[i+1].second].push_back(two[i].second);
        }
    }
    for(int i = 0 ; i < (int)four.size()-1 ; i++) {
        if(four[i+1].first-four[i].first == 2) {
            u.push_back(four[i].second);
            v.push_back(four[i+1].second);
            a.push_back(5);
            b.push_back(four[i].first+1);
            used5[four[i].first+1]=true;
            adj[four[i].second].push_back(four[i+1].second);
            adj[four[i+1].second].push_back(four[i].second);
        }
    }
    for(int i = 0 ; i < (int)six.size()-1 ; i++) {
        if(six[i+1].first-six[i].first == 2) {
            u.push_back(six[i].second);
            v.push_back(six[i+1].second);
            a.push_back(7);
            b.push_back(six[i].first+1);
            adj[six[i].second].push_back(six[i+1].second);
            adj[six[i+1].second].push_back(six[i].second);
        }
    }
    if((int)two.size() > 0 && (int)four.size() > 0) {
        for(int i = 0 ; i < two.size() ; i++) {
            int left=0,right=four.size()-1;
            while(left <= right) {
                int mid = (left+right)/2;
                if(four[mid].first == two[i].first) {
                    u.push_back(two[i].second);
                    v.push_back(four[mid].second);
                    a.push_back(3);
                    b.push_back(two[i].first+1);
                    used3[two[i].first+1]=true;
                    adj[two[i].second].push_back(four[mid].second);
                    adj[four[mid].second].push_back(two[i].second);
                    break;
                }
                if(four[mid].first < two[i].first) {
                    left=mid+1;
                } else {
                    right=mid-1;
                }
            }
        }
    }
    if((int)four.size() > 0 && (int)six.size() > 0) {
        for(int i = 0 ; i < four.size() ; i++) {
            int left=0,right=six.size()-1;
            while(left <= right) {
                int mid = (left+right)/2;
                if(six[mid].first == four[i].first) {
                    int c = used5[four[i].first+1]?-1:1;
                    u.push_back(four[i].second);
                    v.push_back(six[mid].second);
                    a.push_back(5);
                    b.push_back(four[i].first+c);
                    adj[four[i].second].push_back(six[mid].second);
                    adj[six[mid].second].push_back(four[i].second);
                    break;
                }
                if(six[mid].first < four[i].first) {
                    left=mid+1;
                } else {
                    right=mid-1;
                }
            }
        }
    }
    stack<int>s;
    s.push(0);
    vector<bool>vis(x.size(),false);
    while(!s.empty()) {
        int node = s.top();
        s.pop();
        vis[node]=true;
        for(auto z : adj[node]) {
            if(!vis[z]) s.push(z);
        }
    }
    bool f=true;
    for(auto z : vis) {
        if(!z) {
            f=false; break;
        }
    }
    if(f) {
        build(u,v,a,b);
        return 1;
    }
    return 0;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:8:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i = 0 ; i < y.size() ; i++) {
      |                     ~~^~~~~~~~~~
parks.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i = 0 ; i < two.size() ; i++) {
      |                         ~~^~~~~~~~~~~~
parks.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 0 ; i < four.size() ; i++) {
      |                         ~~^~~~~~~~~~~~~

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