Zadanie Midas finał XXIV OI

Question

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!

Comments

Czy zamiana na double na pewno pomoże?

---

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) 

---

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

---

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.

Answer 1

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
*/

 

Comments

Na ile poszło? 100/100 ?

---

tak

---

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.

---

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