Rezultati

Up. imeNalogaJezikRezultatČas oddaje
the-org-2019 Barvanje drevesa C++ 100/100OK 24. apr '19 @ 18:22

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 3,059 MiB 0,000 s OK
#2 [več] 10/10 3,063 MiB 0,000 s OK
#3 [več] 10/10 3,215 MiB 0,000 s OK
#4 [več] 10/10 3,059 MiB 0,004 s OK
#5 [več] 10/10 3,063 MiB 0,000 s OK
#6 [več] 10/10 3,113 MiB 0,004 s OK
#7 [več] 10/10 3,113 MiB 0,004 s OK
#8 [več] 10/10 3,363 MiB 0,000 s OK
#9 [več] 10/10 3,113 MiB 0,000 s OK
#10 [več] 10/10 3,109 MiB 0,010 s OK

Ocenjevani program (main.cpp):
#include <bits/stdc++.h>

#define f first
#define s second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;

const int maxn = 1000 + 17;

int N;
int col, mxl;
vector<int> tree[maxn];
vector<int> lvl[maxn];

int root;
int ans[maxn];

bool ptd[maxn];

int par[maxn];

void DFSPAR(int u)
{
    for (int v : tree[u]) par[v] = u, DFSPAR(v);
}

void DFS2COL(int u, int c)
{
    ans[u] = c;
    for (int v : tree[u]) DFS2COL(v, c ^ 1);
}

void DFSLVL(int u, int l)
{
    mxl = max(mxl, l);
    lvl[l].push_back(u);
    for (int v : tree[u]) DFSLVL(v, l + 1);
}

bool f(int u)
{
    cout << u << endl;
    for (int i = 1; i <= N; i++) cout << i << " " << ans[i] << endl; cout << endl;
    return false;
}

void DFS(int u)
{
    if (ans[u] != -1) return;

    int mask = 0;
    for (int v : tree[u]) if (ans[v] != -1) mask |= 1 << ans[v];

    for (int i = 0; i < 3; i++)
        if (!(mask & (1 << i))) {
            ans[u] = i;
            break;
        }
    
    for (int v : tree[u]) if (ans[v] == -1) DFS(v);
}

/**
15 
2 3
4 5
6 7
8 9
10 11
12 13
14 15
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

**/

int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++) {
        int a, b; cin >> a >> b;
        if (a) tree[i].push_back(a);
        if (b) tree[i].push_back(b);
        col = max(col, 1 + !!a + !!b);
        ptd[a] = ptd[b] = true;
    }

    int _ = 0;
    for (int i = 1; i <= N; i++) if (!ptd[i]) root = i, _++;

    if (col == 2) {
        DFS2COL(root, 0);
        for (int i = 1; i <= N; i++) cout << ++ans[i] << " "; cout << endl;
        return 0;
    }


    DFSLVL(root, 0);

    DFSPAR(root);

    for (int i = 0; i <= mxl; i++)
        for (int j = 0; j < lvl[i].size() - 1; j++)
            tree[lvl[i][j    ]].push_back(lvl[i][j + 1]),
            tree[lvl[i][j + 1]].push_back(lvl[i][j    ]);
    
    for (int i = 1; i <= N; i++) if (i != root) tree[i].push_back(par[i]);
    
    memset(ans, 0xFF, sizeof ans);
    ans[root] = 0;
    for (int i = 0; i <= mxl; i++) {
        for (int j = 0; j < lvl[i].size(); j++) {
            int mask = 0, u = lvl[i][j];
            for (int v : tree[u]) if (ans[v] != -1) mask |= 1 << ans[v];

            for (int i = 0; i < 3; i++)
                if (!(mask & (1 << i))) {
                    ans[u] = i;
                    break;
                }
        }
    }

    for (int i = 1; i <= N; i++) cout << ++ans[i] << " "; cout << endl;
    return 0;
}