Submission #26161

#	Time	Username	Problem	Language	Result	Execution time	Memory
26161		tlwpdus	Snowy Roads (JOI16_snowy)	C++98	100 / 100	22 ms	4192 KiB

Anya

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

using namespace std;

typedef pair<int,int> pii;

static int n;
static vector<pii> lis[600];
static const int MD = 11;
static int chk[600];
static int dis[600];
static int lab[600];
static int par[600];
static int pae[600];
static int cnt;

static void dfs(int here, int p) {
    int i;
    par[here] = p;
    dis[here] = 0;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i].first;
        if (there==p) continue;
        dfs(there,here);
        pae[there] = lis[here][i].second;
        dis[here] = max(dis[here],dis[there]+1);
    }
    if (dis[here]==MD) {
        chk[here] = cnt;
        lab[cnt++] = here;
        dis[here] = -1;
    }
}

void InitAnya(int N , int A[] , int B[]) {
    n = N;
    int i;
    for (i=0;i<500;i++) lis[i].clear();
    memset(chk,-1,sizeof(chk));
    cnt = 0;
    for (i=0;i<n-1;i++) {
        lis[A[i]].push_back(pii(B[i],i));
        lis[B[i]].push_back(pii(A[i],i));
    }
    dfs(0,-1);
}

static int sdis[600];
void fdfs(int here, int p, int d, int C[]) {
    int i;
    sdis[here] = d;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i].first;
        if (there==p) continue;
        fdfs(there,here,d+C[lis[here][i].second],C);
    }
}

void put(int idx, int val) {
    int i;
    for (i=idx+8;i>=idx;i--) {
        Save(i,val%2);
        val>>=1;
    }
}
void Anya(int C[]) {
    int i;
    fdfs(0,-1,0,C);
    for (i=0;i<cnt;i++) put(500+i*9,sdis[lab[i]]);
    for (i=0;i<n-1;i++) Save(i,C[i]);
}

Boris

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

using namespace std;

typedef pair<int,int> pii;

static int n;
static vector<pii> lis[600];
static const int MD = 11;
static int chk[600];
static int dis[600];
static int lab[600];
static int par[600];
static int pae[600];
static int cnt;

static void dfs(int here, int p) {
    int i;
    par[here] = p;
    dis[here] = 0;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i].first;
        if (there==p) continue;
        dfs(there,here);
        pae[there] = lis[here][i].second;
        dis[here] = max(dis[here],dis[there]+1);
    }
    if (dis[here]==MD) {
        chk[here] = cnt;
        lab[cnt++] = here;
        dis[here] = -1;
    }
}

void InitBoris(int N , int A[] , int B[]) {
    n = N;
    int i;
    for (i=0;i<500;i++) lis[i].clear();
    memset(chk,-1,sizeof(chk));
    for (i=0;i<n-1;i++) {
        lis[A[i]].push_back(pii(B[i],i));
        lis[B[i]].push_back(pii(A[i],i));
    }
    dfs(0,-1);
}

int bok(int idx) {
    int res = 0, i;
    for (i=idx;i<idx+9;i++) {
        res *= 2;
        res += Ask(i);
    }
    return res;
}

int Boris(int city) {
    int p = city, res = 0;
    while(p!=0&&chk[p]==-1) {
        res += Ask(pae[p]);
        p = par[p];
    }
    if (p) res += bok(500+9*chk[p]);
    return res;
}

Compilation message (stderr)

Anya.cpp: In function 'void dfs(int, int)':
Anya.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^
Anya.cpp: In function 'void fdfs(int, int, int, int*)':
Anya.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^

Boris.cpp: In function 'void dfs(int, int)':
Boris.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^

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