Submission #1158881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158881		modwwe	Amusement Park (JOI17_amusement_park)	C++20	77 / 100	48 ms	13380 KiB

Joi

#include "Joi.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf = 1e9;
const ll mod2 = 1e9+7;
//const ll base=67;
int  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root;
int kk;
int t;
int el = 19;
bool go[100001];
int in[100001];
int send[100001];
int bi[100001];
int par[100001];
int depth[100001];
int sz[100001];
vector<int> ke[100001];
vector<int> v[100001];
map<int,bool>can[100001];
bool cmp(int x,int y)
{
    return depth[x]>depth[y];
}
void dfs(int x)
{
    go[x]=1;
    depth[x]=0;
    sz[x]=1;
    for(auto f:ke[x])
        if(!go[f])
        {
            /// v[x].pb(f);
            can[x][f]=can[f][x]=1;
            par[f]=x;
            dfs(f);
            sz[x]+=sz[f];
            depth[x]=max(depth[x],depth[f]);
        }
    depth[x]++;
    sort(ke[x].begin(),ke[x].end(),cmp);
    for(auto f:ke[x])
        if(par[f]==x)
            v[x].pb(f);
}
void dfs2(int x)
{
    in[x]=++dem;
    for(auto f:v[x])
        dfs2(f);
}
void Joi(int N,int M,int A[],int B[],ll X,int T)
{
    n=N;
    m=M;
    for(int i=0; i<m; i++)
        ke[A[i]].pb(B[i]),
        ke[B[i]].pb(A[i]);
    dem=0;
    dfs(0);
    dfs2(0);
    long long s=0;
    for(int i=0; i<60; i++)
        bi[i]=bit(X,i),s+=mask(i)*bi[i];
    for(int i=0; i<n; i++)
        MessageBoard(i,bi[in[i]%60]);
}

Ioi

#include "Ioi.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf = 1e9;
const ll mod2 = 1e9+7;
//const ll base=67;
int  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root;
int kk;
int t;
int el = 19;
bool go[100001];
int in[100001];
int send[100001];
int bi[100001];
int par[100001];
int depth[100001];
int sz[100001];
vector<int> ke[100001];
vector<int> v[100001];
map<int,bool>can[100001];
bool cmp(int x,int y)
{
    return depth[x]>depth[y];
}
void dfs(int x)
{
    go[x]=1;
    depth[x]=0;
    sz[x]=1;
    for(auto f:ke[x])
        if(!go[f])
        {
            /// v[x].pb(f);
            can[x][f]=can[f][x]=1;
            par[f]=x;
            dfs(f);
            sz[x]+=sz[f];
            depth[x]=max(depth[x],depth[f]);
        }
    depth[x]++;
    sort(ke[x].begin(),ke[x].end(),cmp);
    for(auto f:ke[x])
        if(par[f]==x)
            v[x].pb(f);
}
void dfs2(int x)
{
    in[x]=++dem;
    for(auto f:v[x])
        dfs2(f);
}
vector<int> dir;
void dfs3(int x)
{
     for(auto f:v[x])
     { if(in[f]<in[root]+60)
       dir.pb(x);
         dfs3(f);
        if(in[f]<in[root]+60)
            dir.pb(f);
     }
}
long long Ioi(int N,int M,int A[],int B[],int P,int V,int T)
{
    n=N;
    m=M;
    for(int i=0; i<n; i++)
        ke[i].clear(),v[i].clear(),go[i]=0;
    for(int i=0; i<m; i++)
    {
        ke[A[i]].pb(B[i]),
        ke[B[i]].pb(A[i]);
    }
    dem=0;
    dfs(0);
    dfs2(0);
    dem=1;
    int start=P;
    int point=V;
    root=start;
    while(sz[start]<60)
    {
        point=Move(par[start]);
        start=par[start];
    }
    dfs3(start);
    set<int> s;
    long long ans=0;
    while(s.size()<60)
    {
        s.insert(in[start]%60);
        if(point)ans|=mask(in[start]%60);
        if(s.size()==60) break;
        point=Move(dir.back());
        start=dir.back();
        dir.pop_back();
    }
    return ans;
}

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