Submission #99874

#	Time	Username	Problem	Language	Result	Execution time	Memory
99874		TAISA_	Snowy Roads (JOI16_snowy)	C++14	20 / 100	49 ms	1892 KiB

Anya

#include <bits/stdc++.h>
#include "Anyalib.h"
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-9;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
vector<vector<P>> G;
vector<int> a,b;
int id;
int n;
void InitAnya(int N,int A[],int B[]){
    n=N;
    a.resize(N-1);
    b.resize(N-1);
    for(int i=0;i<N-1;i++){
        a[i]=A[i];
        b[i]=B[i];
    }
}
void dfs(int i,int p,int sum,int dep){
    if(dep%9==0){
        for(int i=0;i<9;i++){
            if(sum&(1<<i)){
                Save(n+id*9+i,1);
            }
        }
        id++;
    }
    for(auto e:G[i]){
        if(e.first==p)continue;
        Save(e.first,e.second);
        dfs(e.first,i,sum+e.second,dep+1);
    }
}
void Anya(int C[]){
    G.clear();
    G.resize(n);
    id=0;
    for(int i=0;i<n-1;i++){
        G[a[i]].push_back(P(b[i],C[i]));
        G[b[i]].push_back(P(a[i],C[i]));
    }
    dfs(0,-1,0,0);
}

Boris

#include <bits/stdc++.h>
#include "Borislib.h"
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-9;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
vector<vector<int>> G;
vector<int> a,b,idx,par,d;
int n,id;
void dfs(int i,int p,int dep){
    if(dep%9==0){
        idx[i]=id;
        id++;
    }
    d[i]=dep;
    par[i]=p;
    for(auto e:G[i]){
        if(e==p)continue;
        dfs(e,i,dep+1);
    }
}
void InitBoris(int N,int A[],int B[]){
    n=N;
    a.resize(N-1);
    b.resize(N-1);
    idx.resize(n,-1);
    par.resize(n,-1);
    d.resize(n);
    G.resize(n);
    id=0;
    for(int i=0;i<N-1;i++){
        a[i]=A[i];
        b[i]=B[i];
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    dfs(0,-1,0);
}
int Boris(int city){
    int v=city;
    int res=0;
    while(1){
        if(d[v]%9==0){
            int k=idx[v];
            for(int i=0;i<9;i++){
                if(Ask(n+9*k+i)){
                    res+=(1<<i);
                }
            }
            break;
        }else{
            res+=Ask(v);
        }
        v=par[v];
    }
    return res;
}

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