Submission #1053049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053049		tolbi	Fountain Parks (IOI21_parks)	C++17	15 / 100	309 ms	34580 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
//void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);
struct DSU{
    vector<int> par;
    int tot;
    DSU(int n):tot(n){
        par.resize(n);
        iota(par.begin(), par.end(), 0);
    }
    int find(int node){
        if (par[node]==node) return node;
        return par[node]=find(par[node]);
    }
    bool merge(int a, int b){
        a=find(a);
        b=find(b);
        if (a!=b) tot--;
        else return false;
        par[a]=b;
        return true;
    }
};
int construct_roads(vector<int> x, vector<int> y) {
    bool subtask3 = true;
    int n = x.size();
    map<pair<int,int>,int> mp;
    for (int i = 0; i < n; i++){
        mp[{x[i],y[i]}]=i;
        if (x[i]<2 || x[i]>6) subtask3=false;
    }
    if (subtask3){
        DSU dsu(n);
        vector<int> u;
        vector<int> v;
        vector<int> xa;
        vector<int> ya;
        set<pair<int,int>> occupied;
        vector<int> lol;
        for (int i = 0; i < n; ++i)
        {
            if (mp.count({x[i]-2,y[i]})){
                if (dsu.merge(i,mp[{x[i]-2,y[i]}])){
                    u.push_back(mp[{x[i]-2,y[i]}]);
                    v.push_back(i);
                    xa.push_back(x[i]-1);
                    if (x[i]==6) ya.push_back(y[i]-1);
                    else ya.push_back(y[i]+1);
                    occupied.insert({xa.back(),ya.back()});
                }
            }
            if (mp.count({x[i],y[i]-2})){
                if (dsu.merge(i,mp[{x[i],y[i]-2}])){
                    u.push_back(mp[{x[i],y[i]-2}]);
                    v.push_back(i);
                    ya.push_back(y[i]-1);
                    if (x[i]==2) xa.push_back(x[i]-1);
                    else if (x[i]==6) xa.push_back(x[i]+1);
                    else {
                        xa.push_back(-1);
                        lol.push_back(x[i]);
                    }
                    if (xa.back()!=-1) occupied.insert({xa.back(),ya.back()});
                }
            }
        }
        reverse(lol.begin(), lol.end());
        bool boolean=true;
        for (int i = 0; i < xa.size(); i++){
            if (xa[i]==-1){
                if (occupied.find({lol.back()+1,ya[i]})==occupied.end()){
                    xa[i]=lol.back()+1;
                }
                else if (occupied.find({lol.back()-1,ya[i]})==occupied.end()){
                    xa[i]=lol.back()-1;
                }
                else {
                    boolean=false;
                    break;
                }
                lol.pop_back();
            }
        }
        if (dsu.tot==1 && boolean) {
            return build(u,v,xa,ya),1;
        }
        return 0;
    }
    else return cout<<"WA"<<endl,0;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int i = 0; i < xa.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