oj.uz

Submission #553856

# Submission time Handle Problem Language Result Execution time Memory
553856 2022-04-27T07:55:21 Z topovik Fountain Parks (IOI21_parks) C++17
0 / 100
 26 ms 38436 KB 
#include <bits/stdc++.h>
#include "parks.h"
#define pb push_back
#define f first
#define s second
#define pi acos(-1)

using namespace std;

typedef long long ll;
typedef long double ld;

const ll oo = 1e9;
const ld eps = (ld)1 / oo;
const ll N = 2e5 + 100;
const ll M = 1e6;

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

vector <pair<int, int> > ans;
map <int, int> mp[N];
map <int, pair<int, int> > mp1[N];
int pred[N];

//void build(vector <int> u, vector <int> v, vector <int> a, vector <int> b)
//{
//    for (int i = 0; i < u.size(); i++) cout << u[i] << " " << v[i] << " " << a[i] << " " << b[i] << endl;
//}

int get(int x)
{
    return ((pred[x] == x) ? x : (pred[x] = get(pred[x])));
}

int unite(int x, int y)
{
     pred[x] = y;
}

int construct_roads (vector<int> x, vector<int> y) {
    std::vector<int> u, v, a, b;
    int n = x.size();
    vector <pair<int, int> > st;
    for (int i = 0; i < n; i++) mp[x[i]][y[i]] = i + 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int x1 = x[i] + step[j][0];
            int y1 = y[i] + step[j][1];
            if (mp[x1][y1] - 1 > i)
            {
                int nx = mp[x1][y1];
                int x2 = (x[i] + x1) / 2;
                int y2 = (y[i] + y1) / 2;
                mp1[x2][y2] = {i + 1, nx};
                for (int c = 0; c < 4; c++)
                {
                    int x3 = x2 + step[c][0] / 2;
                    int y3 = y2 + step[c][1] / 2;
                    if ((x3 & 1) && (y3 & 1)) st.pb({x3, y3});
                }
            }
        }
    }
    sort(st.begin(), st.end());
    reverse(st.begin(), st.end());
    for (int i = 0; i < n; i++) pred[i] = i;
    int kol = n - 1;
    while (!st.empty() && kol > 0)
    {
        pair<int, int> c = st.back();
        st.pop_back();
        int x = c.f, y = c.s;
        for (int i = (((x + y) / 2) & 1) * 2; i <  (((x + y) / 2) & 1) * 2 + 2; i++)
        {
            int x1 = x + step[i][0] / 2;
            int y1 = y + step[i][1] / 2;
            if (mp1[x1].find(y1) != mp1[x1].end())
            {
                c = mp1[x1][y1];
                c.f--, c.s--;
                if (get(c.f) != get(c.s))
                {
                    unite(get(c.f), get(c.s));
                    u.pb(c.f);
                    v.pb(c.s);
                    a.pb(x);
                    b.pb(y);
                    kol--;
                    break;
                }
            }
        }
    }
    if (kol == 0)
    {
        build(u, v, a, b);
        return 1;
    }
    return 0;
}

//int main()
//{
//    int n;
//    cin >> n;
//    vector <int> x(n), y(n);
//    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
//    cout << construct_roads(x, y) << endl;
//}
/*
1
4
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
*/

Compilation message

parks.cpp: In function 'int unite(int, int)':
parks.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
   38 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Runtime error 26 ms 38436 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Runtime error 26 ms 38436 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Runtime error 26 ms 38436 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Runtime error 26 ms 38436 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Runtime error 26 ms 38436 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Runtime error 26 ms 38436 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -