oj.uz

Submission #548396

# Submission time Handle Problem Language Result Execution time Memory
548396 2022-04-13T08:36:44 Z topovik Fountain Parks (IOI21_parks) C++17
0 / 100
 856 ms 28200 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;
int mrk[N];
map <int, int> mp[N];
map <int, int> mp1[N];
pair<int, int> coord[N];
set <pair<int, pair<int, int> > > ms;

void Rec(int x)
{
    queue <int> q;
    q.push(x);
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        int rn = rand() % 4;
        for (int i = 0; i < 4; i++)
        {
            int x1 = coord[x].f + step[(i + rn) % 4][0];
            int y1 = coord[x].s + step[(i + rn) % 4][1];
            if (mp[x1][y1] != 0)
            {
                int nm = mp[x1][y1] - 1;
                if (!mrk[nm])
                {
                    ans.pb({x, nm});
                    mrk[nm] = 1;
                    q.push(nm);
                }
            }
        }
    }
}

//
//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 construct_roads (vector<int> x, vector<int> y) {
    srand(time(NULL));
    for (int i = 0; i < N; i++)
    {
        mrk[i] = 0;
        mp[i].clear();
        mp1[i].clear();
    }
    ans.clear();
    std::vector<int> u, v, a, b;
    int n = x.size();
    for (int i = 0; i < n; i++) coord[i] = {x[i], y[i]};
    for (int i = 0; i < n; i++) mp[x[i]][y[i]] = i + 1;
    mrk[0] = 1;
    Rec(rand() % n);
    if (ans.size() != n - 1) return 0;
    a.resize(n - 1);
    b.resize(n - 1);
    u.resize(n - 1);
    v.resize(n - 1);
    for (int i = 0; i < N; i++) mp[i].clear();
    for (int i = 0; i < n - 1; i++)
    {
        int x1 = (x[ans[i].f] + x[ans[i].s]) / 2;
        int y1 = (y[ans[i].f] + y[ans[i].s]) / 2;
        for (int j = 0; j < 4; j++)
        {
            int x2 = x1 + step[j][0] / 2;
            int y2 = y1 + step[j][1] / 2;
            if ((x2 & 1) && (y2 & 1))
            {
                if (mp[x2][y2] != 0)
                {
                    ms.erase({mp[x2][y2], {x2, y2}});
                }
                mp[x2][y2]++;
                ms.insert({mp[x2][y2], {x2, y2}});
            }
        }
        mp1[x1][y1] = i + 1;
    }
    while (!ms.empty())
    {
        pair<int, pair<int, int> > c = *ms.begin();
        ms.erase(ms.begin());
        if (c.f == 0) continue;
        int x1 = c.s.f, y1 = c.s.s;
        mp[x1][y1] = 0;
        for (int i = 0; i < 4; i++)
        {
            int x2 = x1 + step[i][0] / 2;
            int y2 = y1 + step[i][1] / 2;
            if (mp1[x2][y2] != 0)
            {
                int nom = mp1[x2][y2] - 1;
                a[nom] = x1;
                b[nom] = y1;
                mp1[x2][y2] = 0;
                int x3 = x2 + step[i][0] / 2;
                int y3 = y2 + step[i][1] / 2;
                if (mp[x3][y3] != 0)
                {
                   ms.erase({mp[x3][y3], {x3, y3}});
                   mp[x3][y3]--;
                   ms.insert({mp[x3][y3], {x3, y3}});
                }
                break;
            }
        }
    }
    for (int i = 0; i < n - 1; i++)
        if (a[i] == 0) return construct_roads(x, y);
    for (int i = 0; i < n - 1; i++)
    {
        u[i] = ans[i].f;
        v[i] = ans[i].s;
    }
    build(u, v, a, b);
    return 1;
}
//
//int main()
//{
//    srand(time(NULL));
//    int n;
//    cin >> n;
//    vector <int> x(n), y(n);
//    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
//    construct_roads(x, y);
//}
/*
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 construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:77:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |     if (ans.size() != n - 1) return 0;
      |         ~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19796 KB Output is correct
2 Correct 16 ms 19796 KB Output is correct
3 Correct 13 ms 19872 KB Output is correct
4 Correct 376 ms 20012 KB Output is correct
5 Correct 856 ms 20136 KB Output is correct
6 Correct 13 ms 19796 KB Output is correct
7 Correct 13 ms 19880 KB Output is correct
8 Correct 12 ms 19796 KB Output is correct
9 Incorrect 70 ms 28200 KB Solution announced impossible, but it is possible.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19796 KB Output is correct
2 Correct 16 ms 19796 KB Output is correct
3 Correct 13 ms 19872 KB Output is correct
4 Correct 376 ms 20012 KB Output is correct
5 Correct 856 ms 20136 KB Output is correct
6 Correct 13 ms 19796 KB Output is correct
7 Correct 13 ms 19880 KB Output is correct
8 Correct 12 ms 19796 KB Output is correct
9 Incorrect 70 ms 28200 KB Solution announced impossible, but it is possible.
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19796 KB Output is correct
2 Correct 16 ms 19796 KB Output is correct
3 Correct 13 ms 19872 KB Output is correct
4 Correct 376 ms 20012 KB Output is correct
5 Correct 856 ms 20136 KB Output is correct
6 Correct 13 ms 19796 KB Output is correct
7 Correct 13 ms 19880 KB Output is correct
8 Correct 12 ms 19796 KB Output is correct
9 Incorrect 70 ms 28200 KB Solution announced impossible, but it is possible.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19796 KB Output is correct
2 Correct 16 ms 19796 KB Output is correct
3 Correct 13 ms 19872 KB Output is correct
4 Correct 376 ms 20012 KB Output is correct
5 Correct 856 ms 20136 KB Output is correct
6 Correct 13 ms 19796 KB Output is correct
7 Correct 13 ms 19880 KB Output is correct
8 Correct 12 ms 19796 KB Output is correct
9 Incorrect 70 ms 28200 KB Solution announced impossible, but it is possible.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19796 KB Output is correct
2 Correct 16 ms 19796 KB Output is correct
3 Correct 13 ms 19872 KB Output is correct
4 Correct 376 ms 20012 KB Output is correct
5 Correct 856 ms 20136 KB Output is correct
6 Correct 13 ms 19796 KB Output is correct
7 Correct 13 ms 19880 KB Output is correct
8 Correct 12 ms 19796 KB Output is correct
9 Incorrect 70 ms 28200 KB Solution announced impossible, but it is possible.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19796 KB Output is correct
2 Correct 16 ms 19796 KB Output is correct
3 Correct 13 ms 19872 KB Output is correct
4 Correct 376 ms 20012 KB Output is correct
5 Correct 856 ms 20136 KB Output is correct
6 Correct 13 ms 19796 KB Output is correct
7 Correct 13 ms 19880 KB Output is correct
8 Correct 12 ms 19796 KB Output is correct
9 Incorrect 70 ms 28200 KB Solution announced impossible, but it is possible.
10 Halted 0 ms 0 KB -