Submission #443444

#	Time	Username	Problem	Language	Result	Execution time	Memory
443444		leinad2	Fountain Parks (IOI21_parks)	C++17	70 / 100	505 ms	76500 KiB

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(i=0;i<n;i++)par[i]=i;
    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});
    }
    for(i=0;i++<cnt;)
    {
        if(chk[i])
        {
            if(chk[i]<chk2[i])return 0;
            else vis[i]=1,dfs(i);
        }
    }
    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;
}

Compilation message (stderr)

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:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(i=0;i<v.size();i++)
      |             ~^~~~~~~~~
parks.cpp:58:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     if(_u.size()!=n-1)return 0;
      |        ~~~~~~~~~^~~~~
parks.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(i=0;i<_u.size();i++)
      |             ~^~~~~~~~~~
parks.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(i=0;i<edge.size();i++)par[Find(edge[i].first)]=Find(edge[i].second);
      |             ~^~~~~~~~~~~~
parks.cpp:82:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(i=0;i<edge.size();i++)chk2[Find(edge[i].first)]++;
      |             ~^~~~~~~~~~~~
parks.cpp:83:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(i=0;i<edge.size();i++)
      |             ~^~~~~~~~~~~~
parks.cpp:96:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(i=0;i<_a.size();i++)
      |             ~^~~~~~~~~~
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;
      |                        ^

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