| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 538684 |
2022-03-17T13:35:44 Z |
Mitsubachi |
None (JOI16_snowy) |
C++14 |
|
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.
