• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Midas finał XXIV OI

VPS Starter Arubacloud
0 głosów
802 wizyt
pytanie zadane 7 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mam problem z zadaniem Midas z finału XXIV OI https://szkopul.edu.pl/problemset/problem/wrTmzO9-dzEbLtsRUCdMV2_W/site/?key=statement

Można napisać bruta na long longach, że idę od jedynki i symuluję koszt i na zapytania odpowiadam w O(1), na 15pkt, można go ulepszyć do 60pkt, zmieniając na double z long longów, nie wiem co dalej. Obiło mi się o uszy, że podobno można tu zastosować LCA z zapisem bitowym(co teorytycznie by się zgadzało, bo link do tego zadania jest w temacie masek bitowych na OKI), ale nie wiem jak by to miało działać. Nigdzie nie udało mi się znaleźć omówienia w internecie / YT.

Wydaje mi się, że pomocne może być umieć stwierdzić, która droga jest o większym koszcie, jak znamy ich zapis binarny jeden to iście w lewo, a 0 to iście w prawo

Z góry dziękuję za pomoc i poświęcony czas!
komentarz 7 kwietnia 2023 przez Whistleroosh Maniak (57,360 p.)
Czy zamiana na double na pewno pomoże?
komentarz 7 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Zmieniłem na long double, i przeszło na 87pkt:

#include <iostream>
#include <vector>

using namespace std;
typedef long double ld;

int n = 0, m = 0, a = 0, b = 0;
vector<int> krawedz_lewa;
vector<int> krawedz_prawa;
vector<ld> dp;

inline void DFS(int v, ld val)
{
    dp[v] = val;
    if (krawedz_lewa[v] != -1)
        DFS(krawedz_lewa[v], val * 2);
    if (krawedz_prawa[v] != -1)
        DFS(krawedz_prawa[v], val * 2 + 1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    dp.assign(n+1,-1);
    krawedz_lewa.assign(n+1,-1);
    krawedz_prawa.assign(n+1,-1);
    for (int i = 1; i <= n; ++i)
        cin >> krawedz_lewa[i] >> krawedz_prawa[i];

    DFS(1,0);

    cin >> m;
    while(m--)
    {
        cin >> a >> b;
        if (dp[a] >= dp[b])
            cout << "TAK" << '\n';
        else
            cout << "NIE" << '\n';
    }

    return 0;
}

Chyba mają jakieś średnie testy ułożone(wątpię, żeby było to celowe) 

komentarz 7 kwietnia 2023 przez Whistleroosh Maniak (57,360 p.)
Hmm, rzeczywiście long double na odpowiednich systemach jest trochę lepszy od long logn. Ale 87 to całkiem dobry wynik, można by zrobić parę brutów do pozostałych zadań i łącznie byłoby z ponad 100 punktów :D
komentarz 7 kwietnia 2023 przez Whistleroosh Maniak (57,360 p.)
A co do zadania, to jedna obserwacja jest taka, ze jak idziemy od korzenia cały czas w lewo i potem zrobimy jeden krok w prawo, to drzewo ukorzenione w wierzchołku do którego doszlismy zachowuje się jak zwykłe drzewo binarne (w sensie chodzi o numeracje). Czyli korzeń ma wartość 1, lewy syn 2*1, prawy 2*1 + 1 itd.

1 odpowiedź

+2 głosów
odpowiedź 25 sierpnia 2023 przez Mikołaj Trębacz Użytkownik (540 p.)
wybrane 25 sierpnia 2023 przez pasjonat_algorytmiki
 
Najlepsza

Trochę po czasie ale może komuś się przyda. Generalnie w zadaniu chodzi o to aby stwierdzać wartość wierzchołka na podstawie położenia go w drzewie, można to zrobić bawiąc się w znajdywanie lca i głębokości wierzchołka. Ponizej kod:

#include<bits/stdc++.h>
using namespace std;

#define st first
#define nd second
#define mp make_pair
typedef long long ll;

const int maxn = 2000005;
const int mn = 1000005;
const int d = 1000000; //stala do wierzcholkow w nowym drzewie

vector <int> g[maxn];
int l[mn], r[mn];
int ly[maxn], ry[maxn];
int now[maxn]; //przypisany numer wierzcholka w nowym drzewie

//lca
int pre[maxn];
int roz[maxn];
int p[maxn][21];
int depth[maxn];
bool odw[maxn];
int k=0, order=1, pot=1;


///nowy graf
void pol(int x, int y){ //polacz wierzcholki w nowym drzewie
    if (r[x] != 0){
        if (ry[y] == 0) ry[y] = r[x]+d;
        now[r[x]] = ry[y];
        pol(r[x], ry[y]);
    }

    if (l[x] != 0 && y != d+1){
        if (ly[y] == 0) ly[y] = l[x]+d;
        now[l[x]] = ly[y];
        pol(l[x], ly[y]);
    }
}

void lista_sasiedztwa(int x){
    if (ry[x] != 0){
        g[x].push_back(ry[x]);
        lista_sasiedztwa(ry[x]);
    }
    if (ly[x] != 0){
        g[x].push_back(ly[x]);
        lista_sasiedztwa(ly[x]);
    }
}


///lca
void dfs(int x){ //preorder, tablica przodkow
    odw[x] = true;
    roz[x] = 1;
    pre[x] = order;
    order++;

    for (int i=0; i<g[x].size(); i++){
        if (odw[g[x][i]] == false){
            depth[g[x][i]] = depth[x]+1;
            dfs(g[x][i]);
            roz[x] += roz[g[x][i]];
            p[g[x][i]][0] = x;
        }
    }
}

bool spr(int x, int y){
    if (pre[y] >= pre[x] && pre[y] <= pre[x] + roz[x] - 1){
        return true;
    }
    return false;
}

int lca(int a, int b){
    if (spr(a, b) == true){
        return a;
    }
    else if (spr(b, a) == true){
        return b;
    }

    for(int i=k; i>=0; i--){
        int a0 = p[a][i];
        if (spr(a0, b) == false){
            a = a0;
        }
    }
    return p[a][0];
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n; cin >> n;
	for (int i=1; i<=n; i++){
        cin >> l[i] >> r[i];
	}

    //nowy graf
	int x = 1;
	while (true){
        if (x == 0) break;
        now[x] = d+1;
        pol(x, d+1);
        x = l[x];
	}
	lista_sasiedztwa(d+1);


    //lca
    while (pot <= n){
        pot *= 2;
        k += 1;
    }
    p[d+1][0] = d+1;
    depth[d+1] = 1;
    dfs(d+1);
    for (int i=1; i<=k; i++){
        for (int j=d+1; j<=d+n; j++){
            p[j][i] = p[p[j][i-1]][i-1];
        }
    }

    //zapytania
    int q; cin >> q;
    for (int i=0; i<q; i++){
        int a, b; cin >> a >> b;
        a = now[a];
        b = now[b];
        int lc = lca(a, b);

        int lew = ly[lc];
        int rig = ry[lc];

        if (a == b){
            cout << "TAK\n";
            continue;
        }

        if (depth[a] != depth[b]){
            if (depth[a] > depth[b]){
                cout << "TAK\n";
            }else{
                cout << "NIE\n";
            }
            continue;
        }

        if ((pre[a] >= pre[rig] && pre[a] <= pre[rig]+roz[rig]-1) //a w prawym i b w lewym
                 && (pre[b] >= pre[lew] && pre[b] <= pre[lew]+roz[lew]-1)){
            cout << "TAK\n";
        }
        else if (b == lc){ //b == lc => a jest w poddrzewie b
            cout << "TAK\n";
        }
        else{
            cout << "NIE\n";
        }
    }

}
/*
5
2 5
0 3
0 4
0 0
0 0

12
2 10
3 7
0 4
0 5
0 6
0 0
0 8
9 0
0 0
0 11
0 12
0 0

5
0 2
3 4
0 0
5 0
0 0
*/

 

komentarz 25 sierpnia 2023 przez reaktywny Nałogowiec (42,200 p.)
Na ile poszło? 100/100 ?
komentarz 25 sierpnia 2023 przez Mikołaj Trębacz Użytkownik (540 p.)
tak
komentarz 25 sierpnia 2023 przez Mikołaj Trębacz Użytkownik (540 p.)
Warto jeszcze pomyśleć o takim jakby corne case. Chodzi o to, że każdy skręt w lewo w drzewie to pomnożenie wartości wierzchołka razy 2x, a każdy skręt w prawo 2x+1. Jako, że 1 wierzchołek ma wartość 0 to każdy skręt w lewo od niego tak jakby nic nie zmienia, dalej jesteśmy w tym samym wierzchołku, bo wartość zostaje ta sama. Dlatego należy stworzyć nowy graf lącząc wszystkie wierzchołki O TEJ SAMEJ WARTOŚCI, można to zrobić łatwym dfs, polecam zobaczyć kod.
komentarz 25 sierpnia 2023 przez reaktywny Nałogowiec (42,200 p.)

@Mikołaj Trębacz, No to ładnie! Z kodem się zapoznam.

Podobne pytania

0 głosów
1 odpowiedź 278 wizyt
pytanie zadane 13 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
0 odpowiedzi 433 wizyt
pytanie zadane 22 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 248 wizyt
pytanie zadane 20 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

93,023 zapytań

141,986 odpowiedzi

321,288 komentarzy

62,368 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...