Submission #923181

#	Time	Username	Problem	Language	Result	Execution time	Memory
923181		winter0101	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	22 ms	6196 KiB

Joi

#include<bits/stdc++.h>
#include "Joi.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e4+9;
vector<int>a[maxn];
vector<int>g[maxn];
bool vis[maxn];
void predfs(int u){
vis[u]=1;
for (auto v:a[u]){
if (!vis[v]){
g[u].pb(v);
g[v].pb(u);
predfs(v);
}
}
}
int d[maxn],sub[maxn],p[maxn];
void dfs(int u,int par){
sub[u]=d[u];
for (auto v:g[u]){
if (v==par)continue;
d[v]=d[u]+1;
p[v]=u;
dfs(v,u);
sub[u]=max(sub[u],sub[v]);
}
}
int in[maxn],tme=0;
bool vcl[maxn];
void solve(int u,int par){
in[u]=tme++;
sort(all(a[u]),[](int i,int j){
return vcl[i]<vcl[j];
});
for (auto v:a[u]){
if (v==par)continue;
solve(v,u);
}
}
void add(int u,int v){
a[u].pb(v);
a[v].pb(u);
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for1(i,0,M-1){
a[A[i]].pb(B[i]);
a[B[i]].pb(A[i]);
}
for1(i,0,N-1)sort(all(a[i]));
tme=0;
for1(i,0,N-1){
vcl[i]=in[i]=d[i]=sub[i]=vis[i]=0;
}
predfs(0);
dfs(0,0);
if (sub[0]+1>=60){
for1(i,0,N-1){
long long bit=d[i]%60;
MessageBoard(i,(X>>bit&1ll));
}
return;
}
for1(i,0,N-1)a[i].clear();
int nw=0;
for1(i,0,N-1)if (d[i]>d[nw])nw=i;
for1(i,0,N-1)vis[i]=0;
queue<int>t;
t.push(0);
vis[0]=1;
int tmp=nw;
int cnt=1;
while (tmp!=0){
add(p[tmp],tmp);
vcl[tmp]=vcl[p[tmp]]=1;
vis[tmp]=1;
cnt++;
t.push(tmp);
tmp=p[tmp];
}
while (!t.empty()){
auto u=t.front();
t.pop();
for (auto v:g[u]){
if (vis[v])continue;
if (cnt==60)break;
add(u,v);
vis[v]=1;
t.push(v);
cnt++;
}
}
solve(0,0);
int dem=0;
for1(i,0,N-1){
if (!vis[i]){
MessageBoard(i,0);
}
else {
long long bit=in[i]%60;
MessageBoard(i,(X>>bit&1ll));
}
}
}

Ioi

#include<bits/stdc++.h>
#include "Ioi.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e4+9;
vector<int>a[maxn];
vector<int>g[maxn];
bool vis[maxn];
void predfs(int u){
vis[u]=1;
for (auto v:a[u]){
if (!vis[v]){
g[u].pb(v);
g[v].pb(u);
predfs(v);
}
}
}
int d[maxn],sub[maxn],p[maxn];
void dfs(int u,int par){
sub[u]=d[u];
for (auto v:g[u]){
if (v==par)continue;
d[v]=d[u]+1;
p[v]=u;
dfs(v,u);
sub[u]=max(sub[u],sub[v]);
}
}
int in[maxn],tme=0;
bool vcl[maxn];
void solve(int u,int par){
in[u]=tme++;
sort(all(a[u]),[](int i,int j){
return vcl[i]<vcl[j];
});
for (auto v:a[u]){
if (v==par)continue;
solve(v,u);
}
}
void add(int u,int v){
a[u].pb(v);
a[v].pb(u);
}
bool type[maxn];
bool need[maxn];
int step=0;
void dfs1(int u,int par){
step++;
if (step==60)return;
sort(all(g[u]),[](int i,int j){
return sub[i]>sub[j];
});
for (auto v:g[u]){
if (v==par)continue;
need[v]=1;
type[v]=Move(v);
dfs1(v,u);
break;
}
}
bool fl=false;
void last(int u,int par,int vertice){
if (u==vertice)fl=true;
need[u]=1;
for (auto v:a[u]){
if (v==par)continue;
type[v]=Move(v);
last(v,u,vertice);
if (!fl){
type[u]=Move(u);
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
for1(i,0,N-1){
a[i].clear(),g[i].clear();
}
for1(i,0,M-1){
a[A[i]].pb(B[i]);
a[B[i]].pb(A[i]);
}
for1(i,0,N-1)sort(all(a[i]));
tme=0;
for1(i,0,N-1){
vcl[i]=in[i]=d[i]=sub[i]=vis[i]=0;
}
predfs(0);
dfs(0,0);
if (sub[0]+1>=60){
int u=P;
while (sub[u]-d[u]+1<60){
type[p[u]]=Move(p[u]);
u=p[u];
}
need[u]=1;
type[P]=V;
dfs1(u,p[u]);
long long ans=0;
for1(i,0,N-1){
if (need[i]&&type[i]){
long long bit=d[i]%60;
ans+=(1ll<<bit);
}
}
return ans;
}
for1(i,0,N-1)a[i].clear();
int nw=0;
for1(i,0,N-1)if (d[i]>d[nw])nw=i;
for1(i,0,N-1)vis[i]=0;
queue<int>t;
t.push(0);
vis[0]=1;
int tmp=nw;
int cnt=1;
while (tmp!=0){
add(p[tmp],tmp);
vcl[tmp]=vcl[p[tmp]]=1;
vis[tmp]=1;
cnt++;
t.push(tmp);
tmp=p[tmp];
}
while (!t.empty()){
auto u=t.front();
t.pop();
for (auto v:g[u]){
if (vis[v])continue;
if (cnt==60)break;
add(u,v);
vis[v]=1;
t.push(v);
cnt++;
}
}
solve(0,0);
int u=P;
while (u!=0){
type[p[u]]=Move(p[u]);
u=p[u];
}
need[0]=1;
last(0,0,nw);
long long ans=0;
for1(i,0,N-1){
if (need[i]&&type[i]){
long long bit=in[i]%60;
ans+=(1ll<<bit);
}
}
return ans;
}

Compilation message (stderr)

Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:67:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   67 | vcl[i]=in[i]=d[i]=sub[i]=vis[i]=0;
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~
Joi.cpp:108:5: warning: unused variable 'dem' [-Wunused-variable]
  108 | int dem=0;
      |     ^~~

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:100:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  100 | vcl[i]=in[i]=d[i]=sub[i]=vis[i]=0;
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17