Submission #513708

#	Time	Username	Problem	Language	Result	Execution time	Memory
513708		79brue	Snowy Roads (JOI16_snowy)	C++14	100 / 100	16 ms	1832 KiB

Anya

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

using namespace std;

static int n;
static vector<int> link[502];
static bool mark[502];
static int depth[502];
static int numLoc[502], locCnt;
static int low[502];

static int dfs(int x, int par = -1){
    int maxDepth = 0;
    for(auto y: link[x]){
        if(y == par) continue;
        depth[y] = depth[x] + 1;
        maxDepth = max(dfs(y, x)+1, maxDepth);
    }
    if(maxDepth == 11 || x==0){
        mark[x] = 1;
        numLoc[x] = locCnt;
        locCnt += 9;
        maxDepth = 0;
    }
    return maxDepth;
}

void InitAnya(int N, int A[], int B[]){
    n = N;
    for(int i=0; i<N-1; i++) link[A[i]].push_back(B[i]), link[B[i]].push_back(A[i]);
    locCnt = n;
    dfs(0);
    for(int i=0; i<N-1; i++){
        if(depth[A[i]] > depth[B[i]]) low[i] = A[i];
        else low[i] = B[i];
    }
}

int DP[502];

void dfs2(int x, int par = -1){
    for(auto y: link[x]){
        if(y == par) continue;
        DP[y] += DP[x];
        dfs2(y, x);
    }
}

void Anya(int C[]){
    memset(DP, 0, sizeof(DP));
    for(int i=0; i<n-1; i++){
        DP[low[i]] = C[i];
    }
    dfs2(0);

    for(int i=0; i<n-1; i++) Save(i, C[i]);
    for(int i=0; i<n; i++){
        if(mark[i]){
            for(int j=numLoc[i]; j<numLoc[i]+9; j++){
                int x = j-numLoc[i];
                Save(j, (DP[i]>>x)&1);
            }
        }
    }
}

Boris

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

using namespace std;

static int n;
static vector<int> link[502];
static bool mark[502];
static int depth[502];
static int numLoc[502], locCnt;
static int low[502], edge[502], p[502];

static int dfs(int x, int par = -1){
    int maxDepth = 0;
    for(auto y: link[x]){
        if(y == par) continue;
        depth[y] = depth[x] + 1;
        p[y] = x;
        maxDepth = max(dfs(y, x)+1, maxDepth);
    }
    if(maxDepth == 11 || x==0){
        mark[x] = 1;
        numLoc[x] = locCnt;
        locCnt += 9;
        maxDepth = 0;
    }
    return maxDepth;
}

void InitBoris(int N , int A[] , int B[]) {
    n = N;
    for(int i=0; i<N-1; i++) link[A[i]].push_back(B[i]), link[B[i]].push_back(A[i]);
    locCnt = n;
    dfs(0);
    for(int i=0; i<N-1; i++){
        if(depth[A[i]] > depth[B[i]]) low[i] = A[i];
        else low[i] = B[i];
        edge[low[i]] = i;
    }
}

int Boris(int x){
    int sum = 0;
    while(!mark[x]){
        if(Ask(edge[x])) sum++;
        x = p[x];
    }
    int base = numLoc[x];
    for(int i=0; i<9; i++){
        if(Ask(base+i)) sum += (1<<i);
    }
    return sum;
}

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