Submission #817835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
817835	2023-08-09T17:43:01 Z	alvingogo	Fountain Parks (IOI21_parks)	C++17	Compilation error	0 ms	0 KB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct DSU{
    vector<int> bo,ss;
    void init(int x){
        bo.resize(x);
        ss.resize(x,1);
        iota(bo.begin(),bo.end(),0);
    }  
    int find(int x){
        return bo[x]==x?x:bo[x]=find(bo[x]);
    }
    int merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return 0;
        }
        bo[x]=y;
        ss[y]+=ss[x];
        return 1;
    }
}dsu;

vector<int> au,av,aa,ab;
set<pair<int,int> > vis;
void ag(int a,int b,int c,int d){
    au.push_back(a);
    av.push_back(b);
    dsu.merge(a,b);
    aa.push_back(c);
    ab.push_back(d);
    vis.insert({c,d});
    //cout << a << " " << b << " " << c << " " << d << '\n';
}
int construct_roads(vector<int> x, vector<int> y) {
    vis.clear();
    if (x.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    map<pair<int,int>,int> mp;
    int n=x.size();
    for(int i=0;i<n;i++){
        mp[{x[i],y[i]}]=i;
    }
    dsu.init(n);
    const int dx[4]={0,0,2,-2},dy[4]={2,-2,0,0};
    function<void(pair<int,int>,int)> dfs=[&](pair<int,int> w,int q){
        int a=0,b=0,c=0,d=0;
        if(dx[q]){
            a=b=dx[q]/2;
            c=1;
            d=-1;
        }
        else{
            a=1;
            b=-1;
            c=d=dy[q]/2;
        }
        int e=0,f=0,g=0,h=0;
        int way=2*(1-q/2);
        if(mp.find({w.fs+a,w.sc+c})==mp.end()){
            if(mp.find({w.fs+b,w.sc+d})==mp.end()){
                return;
            }
            way++;
        }
        if(dx[way]){
            e=f=dx[way]/2;
            g=1;
            h=-1;
        }
        else{
            e=1;
            f=-1;
            g=h=dy[way]/2;
        }
        for(int i=w.fs,j=w.sc;;i+=dx[way],j+=dy[way]){
            int sx=i+e,sy=j+g,tx=i+f,ty=j+h;
            if(mp.find({sx,sy})==mp.end() || mp.find({tx,ty})==mp.end()){
                if(way<2){
                    assert(mp.find({sx-dx[way],sy-dy[way]})!=mp.end());
                    assert(mp.find({tx-dx[way],ty-dy[way]})!=mp.end());
                    ag(mp[{sx-dx[way],sy-dy[way]}],mp[{tx-dx[way],ty-dy[way]}],i,j);
                }
                dfs({i,j},way);
                break;
            }
            else{
                if(vis.find({i+dx[way],j+dy[way]})!=vis.end()){
                    break;
                }
                if(way>=2){
                    ag(mp[{sx,sy}],mp[{tx,ty}],i+dx[way],j+dy[way]);
                }
            }
        }
    };
    for(int p=0;p<n;p++){
        int c=x[p]+2,d=y[p];
        if(mp.find({c,d})!=mp.end()){
            if(mp.find({x[p]+2,y[p]+2})!=mp.end() && mp.find({x[p],y[p]+2})!=mp.end()){
                continue;
            }
            int a=mp[{c,d}];
            if(vis.find({x[p]+1,y[p]+1})==vis.end()){
                ag(a,p,x[p]+1,y[p]+1);
                dfs({x[p]+1,y[p]+1},0);
            }
        }
        
    }
    for(int p=0;p<n;p++){
        int c=x[p],d=y[p]+2;
        if(mp.find({c,d})!=mp.end()){
            int a=mp[{c,d}];
            if(vis.find({x[p]+1,y[p]+1})==vis.end()){
                ag(a,p,x[p]+1,y[p]+1);
            }
            else if(vis.find(x[p]-1,y[p]+1)==vis.end()){
                ag(a,p,x[p]-1,y[p]+1);
            }
        }
    }
    if(dsu.ss[dsu.find(0)]!=n){
        return 0;
    }
    build(au,av,aa,ab);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:125:43: error: no matching function for call to 'std::set<std::pair<int, int> >::find(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type)'
  125 |             else if(vis.find(x[p]-1,y[p]+1)==vis.end()){
      |                                           ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from parks.cpp:2:
/usr/include/c++/10/bits/stl_set.h:794:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::find(const key_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  794 |       find(const key_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_set.h:794:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_set.h:798:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::const_iterator std::set<_Key, _Compare, _Alloc>::find(const key_type&) const [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  798 |       find(const key_type& __x) const
      |       ^~~~
/usr/include/c++/10/bits/stl_set.h:798:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_set.h:804:2: note: candidate: 'template<class _Kt> decltype (std::set<_Key, _Compare, _Alloc>::iterator{((std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::set<_Key, _Compare, _Alloc>::find(const _Kt&) [with _Kt = _Kt; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  804 |  find(const _Kt& __x)
      |  ^~~~
/usr/include/c++/10/bits/stl_set.h:804:2: note:   template argument deduction/substitution failed:
parks.cpp:125:43: note:   candidate expects 1 argument, 2 provided
  125 |             else if(vis.find(x[p]-1,y[p]+1)==vis.end()){
      |                                           ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from parks.cpp:2:
/usr/include/c++/10/bits/stl_set.h:810:2: note: candidate: 'template<class _Kt> decltype (std::set<_Key, _Compare, _Alloc>::const_iterator{((const std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::set<_Key, _Compare, _Alloc>::find(const _Kt&) const [with _Kt = _Kt; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  810 |  find(const _Kt& __x) const
      |  ^~~~
/usr/include/c++/10/bits/stl_set.h:810:2: note:   template argument deduction/substitution failed:
parks.cpp:125:43: note:   candidate expects 1 argument, 2 provided
  125 |             else if(vis.find(x[p]-1,y[p]+1)==vis.end()){
      |                                           ^