oj.uz

Submission #1053144

# Submission time Handle Problem Language Result Execution time Memory
1053144 2024-08-11T09:09:59 Z mychecksedad Fountain Parks (IOI21_parks) C++17
0 / 100
 0 ms 348 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
const int N = 3e5+100;

struct Dsu{
    vi p, s;
    void init(int n){
        p.resize(n);
        s.resize(n,1);
        for(int i = 0; i < n; ++i) p[i]=i;
    }
    int find(int v){
        if(p[v]==v) return v;
        return p[v]=find(p[v]);
    }
    void merge(int a, int b){
        a=find(a);b=find(b);
        if(a!=b){
            if(s[a]>s[b]) swap(a,b);
            p[a] = b;
            s[b] += s[a];
        }
    }
};

int arr[4][2] = {{2, 0}, {-2, 0}, {0, 2}, {0, -2}};

int construct_roads(std::vector<int> x, std::vector<int> y) {
  if (x.size() == 1) {
  build({}, {}, {}, {});
    return 1;
  }
  std::vector<int> U, V, a, b;
  // u.push_back(0);
  // v.push_back(1);
  // a.push_back(x[0]+1);
  // b.push_back(y[0]-1);
vector<array<int, 4>> g;
  int n = x.size();
  Dsu d; d.init(n);
  map<pair<int, int>, int> m;
  map<pair<int, int>, int> used;
  for(int i = 0; i < n; ++i){
    m[{x[i], y[i]}] = i + 1;
  }
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < 4; ++j){
      int nx = x[i] + arr[j][0];
      int ny = y[i] + arr[j][1];
      if(m.find({nx, ny}) != m.end()){
        int id = m[{nx, ny}];
        if(id > i) continue;
        int yy = y[i] + ny >> 1;
        int xx = x[i] + nx >> 1;
        int X = x[i], Y = y[i];
        // cout << X << ' ' << Y << ' ' << nx << ' ' << ny << '\n';
        if(nx < X) swap(X, nx), swap(Y, ny);
        if(ny < Y) swap(X, nx), swap(Y, ny);
        if(abs(nx - X) == 2){
          if((X/2+Y/2) % 2){
            g.pb({xx, Y - 1, i + 1, id});
          }else{
            g.pb({xx, Y + 1, i + 1, id});
          }
        }else{
          if((X/2 + Y/2) % 2 == 0){
            g.pb({X - 1, yy, i + 1, id});
          }else{
            g.pb({X + 1, yy, i + 1, id});
          }
        }   
      }
    }
  }
  sort(all(g));
  for(int i = 0; i < g.size(); ++i){
    int u = g[i][2], v = g[i][3];
    --u, --v;
    if(d.find(u) != d.find(v) && used[{g[i][0], g[i][1]}] == 0){
      d.merge(u, v);
      U.pb(u);
      V.pb(v);
      a.pb(g[i][0]);
      b.pb(g[i][1]);
      used[{g[i][0], g[i][1]}] = 1;
    }
  }


  build(U, V, a, b);
  return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:61:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int yy = y[i] + ny >> 1;
parks.cpp:62:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int xx = x[i] + nx >> 1;
parks.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i = 0; i < g.size(); ++i){
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -