Submission #538684

# Submission time Handle Problem Language Result Execution time Memory
538684 2022-03-17T13:35:44 Z Mitsubachi None (JOI16_snowy) C++14
Compilation error
0 ms 0 KB
//g++ 6.cpp -std=c++14 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

#include "snowy.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
//g++ 6.cpp -std=c++14 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#include "snowy.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

Anya.cpp:5:10: fatal error: atcoder/all: No such file or directory
    5 | #include <atcoder/all>
      |          ^~~~~~~~~~~~~
compilation terminated.

Boris.cpp:5:10: fatal error: snowy.h: No such file or directory
    5 | #include "snowy.h"
      |          ^~~~~~~~~
compilation terminated.