Submission #1179399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179399		hyakup	Fountain Parks (IOI21_parks)	C++20	0 / 100	0 ms	328 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
//#define //bug(x) // cout << #x << " " << x << endl;
struct Point{
  int x, y, id; Point( int x = 0, int y = 0, int id = 0 ) : x(x), y(y), id(id) {}
  bool operator < ( Point p ) const{
    if( y == p.y ) return x < p.x;
    return y < p.y;
  }
};

struct Edge{
  int x1, y1, x2, y2; Edge( int a1, int b1, int a2, int b2 ) : x1( min( a1, a2 ) ), x2( max( a1, a2 ) ), y1( min( b1, b2 ) ), y2( max( b1, b2 )){}
  bool operator < ( Edge e ) const{
    if( x1 != e.x1 ) return x1 < e.x1;
    if( x2 != e.x2 ) return x2 < e.x2;
    if( y1  != e.y1 ) return y1 < e.y1;
    return y2 < e.y2;
  }
};

int construct_roads( vector<int> x, vector<int> y ){
  int n = x.size();

  vector<int> pai(n), grau(n);
  iota( pai.begin(), pai.end(), 0 );



  auto find = [&]( Point p, set<Point>& s ){
    return s.find(p) != s.end();
  };

  auto find2 = [&]( Edge p, set<Edge>& s ){
    return s.find(p) != s.end();
  };

  function<int(int)> get_rep = [&]( int a ){
    return (( pai[a] == a ) ? a : pai[a] = get_rep(pai[a]));
  };

  set<Point> s;
  for( int i = 0; i < n; i++ ) s.insert(Point(x[i], y[i], i));

  set<Edge> edges, evitar;

  int cont = 0;

  for( auto cur : s ){
    if( find( Point( cur.x + 2, cur.y, 0 ), s ) ){

      auto it = s.find(Point( cur.x + 2, cur.y, 0 ) );
      grau[it->id]++;
      grau[cur.id]++;

      pai[get_rep(it->id)] = get_rep(cur.id);
      cont++;
      edges.insert(Edge(cur.x, cur.y, cur.x + 2, cur.y) );
    }
  }

  for( auto cur : s ){
    if( find( Point( cur.x, cur.y - 2, 0 ), s ) ){

      auto it = s.find(Point(cur.x, cur.y - 2, 0 ));

      if( get_rep(it->id) != get_rep(cur.id) ){
        pai[get_rep(it->id)] = get_rep(cur.id);
        grau[cur.id]++;
        grau[it->id]++;
        edges.insert(Edge( cur.x, cur.y, cur.x, cur.y - 2 ) );
        cont++;
      }
    }
  }

  map<Point, int> mp;

  for( auto cur : edges ){
    // cout << cur.x1 << " " << cur.y1 << " " << cur.x2 << " " << cur.y2 << endl;
    if( cur.x1 == cur.x2 ){
      mp[Point(cur.x1 - 1, (cur.y1 + cur.y2)/2, 0 )]++;
      mp[Point(cur.x1 + 1, (cur.y1 + cur.y2)/2, 0 )]++;
    }
    else{
      mp[Point( (cur.x1 + cur.x2)/2, cur.y1 - 1, 0 )]++;
      mp[Point( (cur.x1 + cur.x2)/2, cur.y1 + 1, 0 )]++;
    }
  }

  set<pair<int, Point>> ordem;
  set<Point> bancos;
  for( auto [p, val] : mp ) ordem.insert({ val, p }), bancos.insert(p);

  int dx[] = { 1, 1, -1, -1 };
  int dy[] = { 1, -1, -1, 1 };

  vector<int> resp[4];

  while( !ordem.empty() ){
    auto [val, p] = *ordem.begin(); ordem.erase(ordem.begin());
    bancos.erase(p);

    bool ok = false;

    // cout << "---- " << p.x << " " << p.y << endl;
    for( int d1 = 0, d2 = 1; d1 < 4 && !ok ; d1++, d2 = ( d2 + 1 )%4 ){
      int x1 = p.x + dx[d1], y1 = p.y + dy[d1];
      int x2 = p.x + dx[d2], y2 = p.y + dy[d2];
      int x3 = p.x + dx[d1] + dx[d2], y3 = p.y + dy[d1] + dy[d2];

      // //bug(dx[d1]);
      // //bug(dx[d2]);
      // //bug(dy[d1]);
      // //bug(dy[d2]);

      // cout << x3 << " " << y3 << endl;
      //bug(x1);
      //bug(y1);
      //bug(x2);
      //bug(y2);
      Edge e = Edge( x1, y1, x2, y2 );
      //bug(find( Point( x3, y3, 0 ), bancos ));
      //bug(find2( e, edges ));
      if( find2( e, edges ) && !find( Point( x3, y3, 0 ), bancos ) ){
        Point p1 = *s.find( Point( x1, y1, 0 ) ), p2 = *s.find( Point( x2, y2, 0 ) );
        resp[0].push_back(p1.id);
        resp[1].push_back(p2.id);
        resp[2].push_back(p.x);
        resp[3].push_back(p.y);

        ok = true;

        // cout << p1.id << " " << p2.id << " " << p.x << " " << p.y << endl;

        edges.erase(e);

        if( e.x1 == e.x2 ){
          ordem.erase({ mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )});
          mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )]++;
          ordem.insert({ mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )});

          ordem.erase({ mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )});
          mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )]++;
          ordem.insert({ mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )});
        }
        else{
          ordem.erase({ mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )});
          mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )]++;
          ordem.insert({ mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )});

          ordem.erase({ mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )});
          mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )]++;
          ordem.insert({ mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )});

        }
      }
    }

    for( int d1 = 0, d2 = 1; d1 < 4 && !ok ; d1++, d2 = ( d2 + 1 )%4 ){
      int x1 = p.x + dx[d1], y1 = p.y + dy[d1];
      int x2 = p.x + dx[d2], y2 = p.y + dy[d2];
      int x3 = p.x + dx[d1] + dx[d2], y3 = p.y + dy[d1] + dy[d2];
      Edge e = Edge( x1, y1, x2, y2 );
      // cout << x3 << " " << y3 << endl;

      if( find2( e, edges ) ){
        Point p1 = *s.find( Point( x1, y1, 0 ) ), p2 = *s.find( Point( x2, y2, 0 ) );
        resp[0].push_back(p1.id);
        resp[1].push_back(p2.id);
        resp[2].push_back(p.x);
        resp[3].push_back(p.y);

        ok = true;

        // cout << p1.id << " " << p2.id << " " << p.x << " " << p.y << endl;

        edges.erase(e);

        if( e.x1 == e.x2 ){
          ordem.erase({ mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )});
          mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )]++;
          ordem.insert({ mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )});

          ordem.erase({ mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )});
          mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )]++;
          ordem.insert({ mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )});
        }
        else{
          ordem.erase({ mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )});
          mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )]++;
          ordem.insert({ mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )});

          ordem.erase({ mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )});
          mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )]++;
          ordem.insert({ mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )});

        }
      }
    }
    ordem.erase({ mp[p], p });
  }

  build( resp[0], resp[1], resp[2], resp[3] );
  if( cont == n - 1 ) return 1;
  return 0;

  // set<Edge> evitar;
  //
  // for( auto cur : s ){
  //   if( find( Point( cur.x, cur.y - 1, 0 ), s ) && !find( Edge( cur.x, cur.y, cur.x, cur.y - 1 ), evitar ) ){
  //
  //   }
  // }

}

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