oj.uz

Submission #568642

# Submission time Handle Problem Language Result Execution time Memory
568642 2022-05-25T23:23:43 Z zaneyu Amusement Park (JOI17_amusement_park) C++14
0 / 100
 3000 ms 58020 KB 
#include "Joi.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;

#define ld long double
#define pii pair<int,int>
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=6e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())+1
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
namespace {
    vector<int> v[maxn];
    bool vis[maxn];
    int vs=0;
    int id[maxn];
    vector<int> comp[maxn];
    map<pii,int> tr;
    int n;
    void dfs(int u,int p){
        vis[u]=1;
        if(vs<60){
            id[u]=(vs++);
            if(vs==60){
                vector<int> v;
                REP(i,n) if(vis[i]) v.pb(i);
                for(int a:v) comp[a]=v;
            }
        }
        else{
            comp[u]=comp[p];
            comp[u].pb(u);
            map<int,int> cnt;
            for(int a:comp[u]) for(int b:comp[u]){
                if(tr[{a,b}]) cnt[a]++;
            }
            for(auto x:cnt){
                if(x.s==1){
                    comp[u].erase(find(ALL(comp[u]),x.f));
                    break;
                }
            }
            set<int> ids;
            REP(i,60) ids.insert(i);
            for(int a:comp[u]) if(a!=u) ids.erase(id[a]);
            id[u]=(*ids.begin());
        }
        for(int x:v[u]){
            if(!vis[x]){
                tr[{u,x}]=tr[{x,u}]=1;
                dfs(x,u);
            }
        }
    }
}
void Joi(int N, int m, int A[], int B[], long long X, int T) {
    n=N;
    REP(i,m){
        v[A[i]].pb(B[i]);
        v[B[i]].pb(A[i]);
    }
    dfs(0,-1);
    REP(i,n) MessageBoard(i,(X>>id[i])&1);
}

#include "Ioi.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;

#define ld long double
#define pii pair<int,int>
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=6e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())+1
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
namespace {
    vector<int> v[maxn];
    bool vis[maxn];
    int vs=0;
    int id[maxn];
    vector<int> comp[maxn];
    map<pii,int> tr;
    int n;
    void dfs(int u,int p){
        vis[u]=1;
        if(vs<60){
            id[u]=(vs++);
            if(vs==60){
                vector<int> v;
                REP(i,n) if(vis[i]) v.pb(i);
                for(int a:v) comp[a]=v;
            }
        }
        else{
            comp[u]=comp[p];
            comp[u].pb(u);
            map<int,int> cnt;
            for(int a:comp[u]) for(int b:comp[u]){
                if(tr[{a,b}]) cnt[a]++;
            }
            for(auto x:cnt){
                if(x.s==1){
                    comp[u].erase(find(ALL(comp[u]),x.f));
                    break;
                }
            }
            set<int> ids;
            REP(i,60) ids.insert(i);
            for(int a:comp[u]) if(a!=u) ids.erase(id[a]);
            id[u]=(*ids.begin());
        }
        for(int x:v[u]){
            if(!vis[x]){
                tr[{u,x}]=tr[{x,u}]=1;
                dfs(x,u);
            }
        }
    }
    bool in[maxn];
    ll ans=0;
    void dfs2(int u,int p){
        vis[u]=1;
        if(p!=-1) ans|=((int)Move(u)<<id[u]);
        for(int x:v[u]){
            if(!vis[x] and in[x]) dfs2(x,u);
        }   
        if(p!=-1) ans|=((int)Move(p)<<id[p]);
    }
}
long long Ioi(int N, int m, int A[], int B[], int P, int V, int T) {
    n=N;
    REP(i,m){
        v[A[i]].pb(B[i]);
        v[B[i]].pb(A[i]);
    }
    dfs(0,-1);
    REP(i,n) vis[i]=0;
    for(int a:comp[P]) in[a]=1;
    dfs2(P,-1);
    return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 57628 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 48312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 58020 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 47976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 47944 KB Time limit exceeded
2 Halted 0 ms 0 KB -