Submission #26160

#	Time	Username	Problem	Language	Result	Execution time	Memory
26160		tlwpdus	Snowy Roads (JOI16_snowy)	C++98	100 / 100	22 ms	4204 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 pii edg[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 has[600];
static int ras[600];
static int cnt, ent;

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);
        has[lis[here][i].second] = ent;
        ras[ent] = lis[here][i].second;
        lis[here][i].second = ent;
        pae[there] = ent++;
        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; ent = 0;
    for (i=0;i<n-1;i++) {
        if (A[i]>B[i]) swap(A[i],B[i]);
        lis[A[i]].push_back(pii(B[i],i));
        lis[B[i]].push_back(pii(A[i],i));
        edg[i] = pii(A[i],B[i]);
    }
    for (i=0;i<n;i++) sort(lis[i].begin(),lis[i].end());
    dfs(0,-1);
}

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[ras[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(has[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 pii edg[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 has[600];
static int ras[600];
static int cnt, ent;

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);
        has[lis[here][i].second] = ent;
        ras[ent] = lis[here][i].second;
        lis[here][i].second = ent;
        pae[there] = ent++;
        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++) {
        if (A[i]>B[i]) swap(A[i],B[i]);
        lis[A[i]].push_back(pii(B[i],i));
        lis[B[i]].push_back(pii(A[i],i));
        edg[i] = pii(A[i],B[i]);
    }
    for (i=0;i<n;i++) sort(lis[i].begin(),lis[i].end());
    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:25: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:62: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:25: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