Submission #538687

#	Time	Username	Problem	Language	Result	Execution time	Memory
538687		Mitsubachi	Snowy Roads (JOI16_snowy)	C++14	100 / 100	20 ms	1904 KiB

Anya

//g++ 6.cpp -std=c++14 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#include "Anyalib.h"

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;

#define fi first
#define se second
#define pb push_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

using P = pair<int,int>;

/*
vi server(1000,0);

void Save(int place,int bit){
  server[place]=bit;
  return;
}

int Ask(int place){
  return server[place];
}
*/

// Anya start

//recordAnyaのやつには答えを入れる　他のは親から+1されたかを入れる
int nAnya;
vvi gAnya(550);
vi seenAnya(550,0),distAnya(550),parentAnya(550,-1),addAnya(550),ansAnya(550),disAnya(550);
vector<P> edgeAnya(550),recordAnya;
int usedAnya=0;

int digitAnya(int x){
  int res=0;
  while(x>0){
    res++;
    x/=2;
  }
  return res;
}

void dfsAnya(int now,vvi &g,vi &seen,vi &dist,vi &parent,vector<P> &record,int bit){
  seen[now]=1;
  if(usedAnya==0&&bit>10){
    usedAnya=1;
    record.emplace_back(now,digitAnya(dist[now]));
    bit=digitAnya(dist[now]);
  }
  if(bit>20){
    usedAnya=1;
    record.emplace_back(now,digitAnya(dist[now]));
    bit=digitAnya(dist[now]);
  }
  for(int next:g[now]){
    if(seen[next]==1)continue;
    dist[next]=dist[now]+1;
    parent[next]=now;
    dfsAnya(next,g,seen,dist,parent,record,bit+1);
  }
}

void dfsAnya2(int now,vvi &g,vi &seen,vi &ans,vi &add){
  seen[now]=1;
  for(int next:g[now]){
    if(seen[next]==1)continue;
    ans[next]=ans[now];
    if(add[next]==1){
      ans[next]++;
    }
    dfsAnya2(next,g,seen,ans,add);
  }
}

void InitAnya(int N,int A[],int B[]){
  nAnya=N;
  rep(i,0,nAnya){
    disAnya[i]=1;
  }
  rep(i,0,nAnya-1){
    gAnya[A[i]].emplace_back(B[i]);
    gAnya[B[i]].emplace_back(A[i]);
    edgeAnya[i]={A[i],B[i]};
  }
  
  distAnya[0]=0;
  dfsAnya(0,gAnya,seenAnya,distAnya,parentAnya,recordAnya,0);
  
  sort(all(recordAnya));
  int need=nAnya;
  for(auto [place,bit]:recordAnya){
    need+=bit-1;
    disAnya[place]=0;
  }

  if(need>1000){
    recordAnya.clear();
    rep(i,0,nAnya){
      seenAnya[i]=0;
      disAnya[i]=1;
    }
    dfsAnya(0,gAnya,seenAnya,distAnya,parentAnya,recordAnya,0);
    need=nAnya;
    for(auto [place,bit]:recordAnya){
      need+=bit-1;
      disAnya[place]=0;
    }
  }
  return;
}

void Anya(int C[]){
  rep(i,0,nAnya){
    addAnya[i]=0;
    seenAnya[i]=0;
    ansAnya[i]=0;
  }
  rep(i,0,nAnya-1){
    if(C[i]==1){
      int u=edgeAnya[i].fi,v=edgeAnya[i].se;
      if(parentAnya[u]==v){
        addAnya[u]++;
      }
      else{
        addAnya[v]++;
      }
    }
  }

  dfsAnya2(0,gAnya,seenAnya,ansAnya,addAnya);

  int now=0;
  for(auto [place,bit]:recordAnya){
    int x=ansAnya[place];
    rep(i,0,bit){
      Save(now,x%2);
      now++;
      x/=2;
    }
  }
  rep(i,0,nAnya){
    if(disAnya[i]==1){
      Save(now,addAnya[i]);
      now++;
    }
  }

  return;
}

// Anya end

Boris

//g++ 6.cpp -std=c++14 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#include "Borislib.h"

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;

#define fi first
#define se second
#define pb push_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

using P = pair<int,int>;

/*
vi server(1000,0);

void Save(int place,int bit){
  server[place]=bit;
  return;
}

int Ask(int place){
  return server[place];
}
*/

// Boris start

int nBoris;
vvi gBoris(550);
vi seenBoris(550,0),distBoris(550),parentBoris(550,-1),addBoris(550),ansBoris(550),disBoris(550);
vector<P> edgeBoris(550),recordBoris,placeBoris(550);
int usedBoris=0;

int digitBoris(int x){
  int res=0;
  while(x>0){
    res++;
    x/=2;
  }
  return res;
}

void dfsBoris(int now,vvi &g,vi &seen,vi &dist,vi &parent,vector<P> &record,int bit){
  seen[now]=1;
  if(usedBoris==0&&bit>10){
    usedBoris=1;
    record.emplace_back(now,digitBoris(dist[now]));
    bit=digitBoris(dist[now]);
  }
  if(bit>20){
    usedBoris=1;
    record.emplace_back(now,digitBoris(dist[now]));
    bit=digitBoris(dist[now]);
  }
  for(int next:g[now]){
    if(seen[next]==1)continue;
    dist[next]=dist[now]+1;
    parent[next]=now;
    dfsBoris(next,g,seen,dist,parent,record,bit+1);
  }
  return;
}

void InitBoris(int N,int A[],int B[]){
  nBoris=N;
  rep(i,0,nBoris){
    disBoris[i]=1;
  }
  rep(i,0,nBoris-1){
    gBoris[A[i]].emplace_back(B[i]);
    gBoris[B[i]].emplace_back(A[i]);
    edgeBoris[i]={A[i],B[i]};
  }

  distBoris[0]=0;
  dfsBoris(0,gBoris,seenBoris,distBoris,parentBoris,recordBoris,0);
  
  sort(all(recordBoris));
  int now=0;
  for(auto [place,bit]:recordBoris){
    disBoris[place]=0;
    placeBoris[place]={now,now+bit-1};
    now+=bit;
  }

  rep(i,0,nBoris){
    if(disBoris[i]==1){
      placeBoris[i]={now,now};
      now++;
    }
  }

  if(now>1000){
    now=0;
    recordBoris.clear();
    rep(i,0,nBoris){
      seenBoris[i]=0;
      disBoris[i]=1;
    }
    dfsBoris(0,gBoris,seenBoris,distBoris,parentBoris,recordBoris,0);
    for(auto [place,bit]:recordBoris){
      disBoris[place]=0;
      placeBoris[place]={now,now+bit-1};
      now+=bit;
    }
    rep(i,0,nBoris){
      if(disBoris[i]==1){
        placeBoris[i]={now,now};
        now++;
      }
    }
  }
  return;
}

int ans(int city){
  if(city==0){
    return 0;
  }
  auto [p,q]=placeBoris[city];
  if(disBoris[city]==0){
    int res=0,bit=1;
    rep(i,p,q+1){
      int x=Ask(i);
      res+=bit*x;
      bit*=2;
    }
    return res;
  }
  else{
    int x=Ask(p);
    return ans(parentBoris[city])+x;
  }
}

int Boris(int city){
  int res=ans(city);
  return res;
}

// Boris end

Compilation message (stderr)

Anya.cpp: In function 'void InitAnya(int, int*, int*)':
Anya.cpp:108:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |   for(auto [place,bit]:recordAnya){
      |            ^
Anya.cpp:121:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |     for(auto [place,bit]:recordAnya){
      |              ^
Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:150:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  150 |   for(auto [place,bit]:recordAnya){
      |            ^

Boris.cpp: In function 'void InitBoris(int, int*, int*)':
Boris.cpp:96:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |   for(auto [place,bit]:recordBoris){
      |            ^
Boris.cpp:117:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |     for(auto [place,bit]:recordBoris){
      |              ^
Boris.cpp: In function 'int ans(int)':
Boris.cpp:136:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  136 |   auto [p,q]=placeBoris[city];
      |        ^

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