Submission #288027

#	Time	Username	Problem	Language	Result	Execution time	Memory
288027		Alexa2001	Snowy Roads (JOI16_snowy)	C++17	100 / 100	25 ms	2120 KiB

Anya

#include "Anyalib.h"
#include <bits/stdc++.h>

using namespace std;

static int getL;

namespace
{
    const int Nmax = 1005;
    vector<int> v[Nmax];
    int n, w[Nmax], t[Nmax];
    bool special[Nmax];

    pair<int,int> edge[Nmax];


    void dfs0(int node, int dad = -1)
    {
        w[node] = 0;
        t[node] = dad;

        for(auto it : v[node])
            if(it != dad)
            {
                dfs0(it, node);
                w[node] = max(w[it], w[node]);
            }

        if(w[node] == 9)
        {
            w[node] = 0;
            special[node] = 1;
        }
        else ++w[node];
    }

    void dfs(int node, int dad, int C[])
    {
         for(auto it : v[node])
            if(it != dad)
            {
                w[it] += w[node];
                dfs(it, node, C);
            }
    }
};

void InitAnya(int N , int A[] , int B[])
{
    n = N;
    int i;
    for(i=0; i<n-1; ++i)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
        edge[i] = {A[i], B[i]};
    }

    dfs0(0);

    for(i=0; i<n-1; ++i)
        if(t[edge[i].first] == edge[i].second) swap(edge[i].first, edge[i].second);
}

void Anya(int C[])
{
    int i, j;

    for(i=0; i<n; ++i) w[i] = 0;

    for(i=0; i<n-1; ++i)
        w[edge[i].second] += C[i];

    for(i=1; i<n; ++i)
        Save(i, w[i]);

    dfs(0, -1, C);

    int nr = n;

    for(i=0; i<n; ++i)
        if(special[i])
            for(j=8; j>=0; --j)
            {
                Save(nr, (w[i] >> j) & 1);
                ++nr;
            }
}

Boris

#include "Borislib.h"
#include <bits/stdc++.h>

using namespace std;

namespace
{
    const int Nmax = 1005;

    int n;
    vector<int> v[Nmax];
    int w[Nmax], where[Nmax], t[Nmax];
    bool special[Nmax];

    void dfs0(int node, int dad = -1)
    {
        w[node] = 0;
        t[node] = dad;

        for(auto it : v[node])
            if(it != dad)
            {
                dfs0(it, node);
                w[node] = max(w[it], w[node]);
            }

        if(w[node] == 9)
        {
            w[node] = 0;
            special[node] = 1;
        }
        else ++w[node];
    }
};


void InitBoris(int N , int A[] , int B[])
{
    n = N;
    int i;
    for(i=0; i<n-1; ++i)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
    }
    dfs0(0);

    int nr = n;

    for(i=0; i<n; ++i)
        if(special[i])
        {
            where[i] = nr;
            nr += 9;
        }
}

int Boris(int x)
{
    if(x == 0) return 0;

    if(special[x])
    {
        int ans = 0, i;
        for(i = where[x]; i < where[x] + 9; ++i)
            ans = 2 * ans + Ask(i);
        return ans;
    }

    return Ask(x) + Boris(t[x]);
}

Compilation message (stderr)

Anya.cpp:6:12: warning: 'getL' defined but not used [-Wunused-variable]
    6 | static int getL;
      |            ^~~~

• Subtask 1: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45