oj.uz

Submission #1070949

# Submission time Handle Problem Language Result Execution time Memory
1070949 2024-08-22T21:40:28 Z jerzyk Fountain Parks (IOI21_parks) C++17
0 / 100
 1 ms 4444 KB 
#include <bits/stdc++.h>
#include "parks.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
int fau[N];
pair<int, int> tab[N], ntab[N];
map<pair<int, int>, int> pts;
vector<pair<int, int>> ed;
vector<pair<int, int>> ben;
vector<int> ans1, ans2, ans3, ans4;

int Find(int v)
{
    return (fau[v] = (fau[v] == v ? v : Find(fau[v])));
}

void Union(int a, int b)
{
    fau[Find(b)] = Find(a);
}

int Check(int x, int y)
{
    if(pts.find(make_pair(x, y)) != pts.end())
        return pts[make_pair(x, y)];
    return -1;
}

bool Clr(pair<int, int> a)
{
    return ((a.st / 2 + a.nd / 2) % 2 == 0);
}

void MakE(int n)
{
    for(int i = 0; i < n; ++i)
    {
        int v = Check(ntab[i].st, ntab[i].nd);
        int u = Check(ntab[i].st, ntab[i].nd + 2), l = Check(ntab[i].st - 2, ntab[i].nd);
        if(u != -1 && l != -1 && Check(ntab[i].st - 2, ntab[i].nd + 2) != -1)
        {
            //cerr << "XDKURAWdasljlsdfkjakd\n";
            if(Clr(ntab[i])) ed.pb(make_pair(v, u));
            else ed.pb(make_pair(v, l));
            continue;
        }
        if(u != -1)
            ed.pb(make_pair(v, u));
        if(l != -1)
            ed.pb(make_pair(v, l));
    }
}

void SpTree()
{
    vector<pair<int, int>> nxt;
    for(int i = 0; i < (int)ed.size(); ++i)
    {
        cerr << ed[i].st << " " << ed[i].nd << "\n";
        if(Find(ed[i].st) != Find(ed[i].nd))
        {
            Union(ed[i].st, ed[i].nd);
            nxt.pb(ed[i]);
        }
    }
    ed = nxt;
}

void DoB()
{
    for(int i = 0; i < (int)ed.size(); ++i)
    {
        int v = ed[i].st, u = ed[i].nd;
        if(tab[u].st == tab[v].st)
        {
            if(Clr(tab[u]))
                ben.pb(make_pair(tab[u].st + 1, tab[u].nd + 1));
            else
                ben.pb(make_pair(tab[u].st - 1, tab[u].nd + 1));
        }else
        {
            if(Clr(tab[u]))
                ben.pb(make_pair(tab[u].st - 1, tab[u].nd + 1));
            else
                ben.pb(make_pair(tab[u].st + 1, tab[u].nd - 1));
        }
    }
}

void ConstructAnswer()
{
    for(int i = 0; i < (int)ed.size(); ++i)
    {
        ans1.pb(ed[i].st); ans2.pb(ed[i].nd);
        ans3.pb(ben[i].st); ans4.pb(ben[i].nd);
    }
}

int construct_roads(vector<int> _x, vector<int> _y)
{
    int n = _x.size();
    for(int i = 0; i < n; ++i)
    {
        tab[i] = make_pair(_x[i], _y[i]);
        pts[tab[i]] = i;
        fau[i] = i;
        ntab[i] = tab[i];
    }
    sort(ntab, ntab + n);
    MakE(n);
    //cerr << "xd\n";
    SpTree();
    //cerr << "xd\n";
    if((int)ed.size() < n - 1) return 0;
    DoB();
    ConstructAnswer();
    build(ans1, ans2, ans3, ans4);
    return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -