Submission #1053040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053040		tolbi	Fountain Parks (IOI21_parks)	C++17	15 / 100	258 ms	26412 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 subtask2 = true;
    bool subtask3 = true;
    bool subtask5 = 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]>4) subtask2=false;
        if (x[i]<2 || x[i]>6) subtask3=false;
    }
    if (subtask2){        
        DSU dsu(n);
        vector<int> u;
        vector<int> v;
        vector<int> xa;
        vector<int> ya;
        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);
                    ya.push_back(y[i]-1);
                }
            }
            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);
                    if (x[i]==2) xa.push_back(x[i]-1);
                    else xa.push_back(x[i]+1);
                    ya.push_back(y[i]-1);
                }
            }
        }
        if (dsu.tot==1) 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:27:10: warning: variable 'subtask3' set but not used [-Wunused-but-set-variable]
   27 |     bool subtask3 = true;
      |          ^~~~~~~~
parks.cpp:28:10: warning: unused variable 'subtask5' [-Wunused-variable]
   28 |     bool subtask5 = true;
      |          ^~~~~~~~

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