답안 #443492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443492	2021-07-10T15:17:24 Z	leinad2	분수 공원 (IOI21_parks)	C++17	컴파일 오류	0 ms	0 KB

parks

//#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
int par[400010], chk[400010], chk2[400010], A[400010][2], vis[400010];
int Find(int v){return v==par[v]?v:par[v]=Find(par[v]);}
vector<pair<int, int> >v;
int cnt;
map<pair<int, int>, int>mp;
vector<pair<int, int> >adj[400010];
vector<int>_u, _v, _a, _b;
void dfs(int v)
{
    for(int i=0;i<adj[v].size();i++)
    {
        int p=adj[v][i].first;
        if(!vis[p])vis[p]=1,dfs(p),_a[adj[v][i].second]=p;
    }
}
int construct_roads(vector<int>x, vector<int>y)
{
    int n, i, j, k, a, b;
    n=x.size();
    vector<pair<pair<int, int>, int> >V;
    for(i=0;i<n;i++)
    {
        V.push_back({{x[i], y[i]}, i});
    }
    sort(V.begin(), V.end());
    for(i=1;i<V.size();i++)
    {
        if(V[i].first.first==V[i-1].first.first&&V[i].first.second==V[i-1].first.second+2)
        {
            v.push_back({V[i].second, V[i-1].second});
        }
    }
    for(i=0;i<n;i++)
    {
        swap(V[i].first.first, V[i].first.second);
    }
    sort(V.begin(), V.end());
    for(i=1;i<V.size();i++)
    {
        if(V[i].first.first==V[i-1].first.first&&V[i].first.second==V[i-1].first.second+2)
        {
            v.push_back({V[i].second, V[i-1].second});
        }
    }
    for(int rng=0;rng<5;rng++)
    {
        for(i=0;i<n;i++)par[i]=i;
        if(rng!=0)random_shuffle(v.begin(), v.end());
        _u.clear();_v.clear();_a.clear();_b.clear();cnt=0;mp.clear();for(i=1;i<=2*n;i++)vis[i]=chk[i]=chk2[i]=0,adj[i].clear();
        for(i=0;i<v.size();i++)
        {
            if(Find(v[i].first)!=Find(v[i].second))
            {
                _u.push_back(v[i].first);
                _v.push_back(v[i].second);
                par[Find(v[i].first)]=Find(v[i].second);
            }
        }
        if(_u.size()!=n-1)return 0;
        vector<pair<int, int> >edge;
        _a.resize(n-1);_b.resize(n-1);
        for(i=0;i<_u.size();i++)
        {
            int a=_u[i], b=_v[i], q, w, e, r;
            if(x[a]==x[b])
            {
                q=x[a]-1;e=x[a]+1;
                w=r=(y[a]+y[b])/2;
            }
            else
            {
                w=y[a]-1;r=y[a]+1;
                q=e=(x[a]+x[b])/2;
            }
            if(mp.find({q, w})==mp.end())mp[{q, w}]=++cnt,A[cnt][0]=q,A[cnt][1]=w;
            if(mp.find({e, r})==mp.end())mp[{e, r}]=++cnt,A[cnt][0]=e,A[cnt][1]=r;
            int x=mp[{q, w}];int y=mp[{e, r}];
            edge.push_back({x, y});
        }
        for(i=0;i++<cnt;)par[i]=i;
        for(i=0;i<edge.size();i++)par[Find(edge[i].first)]=Find(edge[i].second);
        for(i=0;i++<cnt;)chk[Find(i)]++;
        for(i=0;i<edge.size();i++)chk2[Find(edge[i].first)]++;
        for(i=0;i<edge.size();i++)
        {
            adj[edge[i].first].push_back({edge[i].second, i});
            adj[edge[i].second].push_back({edge[i].first, i});
        }
        bool flag=true;
        for(i=0;i++<cnt;)
        {
            if(chk[i])
            {
                if(chk[i]<chk2[i]){flag=false;break;}
                else vis[i]=1,dfs(i);
            }
        }
        if(!flag)continue;
        for(i=0;i<_a.size();i++)
        {
            if(_a[i]==0)_a[i]=Find(edge[i].first);
            int a=_a[i];
            _a[i]=A[a][0];_b[i]=A[a][1];
        }
        build(_u, _v, _a, _b);
        return 1;
    }
    return 0;
}

Compilation message

parks.cpp: In function 'void dfs(int)':
parks.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(i=1;i<V.size();i++)
      |             ~^~~~~~~~~
parks.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(i=1;i<V.size();i++)
      |             ~^~~~~~~~~
parks.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
parks.cpp:62:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |         if(_u.size()!=n-1)return 0;
      |            ~~~~~~~~~^~~~~
parks.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(i=0;i<_u.size();i++)
      |                 ~^~~~~~~~~~
parks.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(i=0;i<edge.size();i++)par[Find(edge[i].first)]=Find(edge[i].second);
      |                 ~^~~~~~~~~~~~
parks.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(i=0;i<edge.size();i++)chk2[Find(edge[i].first)]++;
      |                 ~^~~~~~~~~~~~
parks.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(i=0;i<edge.size();i++)
      |                 ~^~~~~~~~~~~~
parks.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(i=0;i<_a.size();i++)
      |                 ~^~~~~~~~~~
parks.cpp:108:9: error: 'build' was not declared in this scope
  108 |         build(_u, _v, _a, _b);
      |         ^~~~~
parks.cpp:21:15: warning: unused variable 'j' [-Wunused-variable]
   21 |     int n, i, j, k, a, b;
      |               ^
parks.cpp:21:18: warning: unused variable 'k' [-Wunused-variable]
   21 |     int n, i, j, k, a, b;
      |                  ^
parks.cpp:21:21: warning: unused variable 'a' [-Wunused-variable]
   21 |     int n, i, j, k, a, b;
      |                     ^
parks.cpp:21:24: warning: unused variable 'b' [-Wunused-variable]
   21 |     int n, i, j, k, a, b;
      |                        ^