oj.uz

Submission #568645

# Submission time Handle Problem Language Result Execution time Memory
568645 2022-05-26T00:30:45 Z zaneyu Amusement Park (JOI17_amusement_park) C++14
100 / 100
 404 ms 41200 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=1e4+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];
    bitset<10005> tr[maxn];
    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;
            REP(i,sz(comp[u])) REP(j,i){
                int a=comp[u][i],b=comp[u][j];
                if(tr[a][b]) cnt[i]++,cnt[j]++;
            }
            for(auto x:cnt){
                if(x.s==1){
                    comp[u].erase(comp[u].begin()+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=1e4+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];
    bitset<10005> tr[maxn];
    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;
            REP(i,sz(comp[u])) REP(j,i){
                int a=comp[u][i],b=comp[u][j];
                if(tr[a][b]) cnt[i]++,cnt[j]++;
            }
            for(auto x:cnt){
                if(x.s==1){
                    comp[u].erase(comp[u].begin()+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|=((ll)Move(u)<<id[u]);
        for(int x:v[u]){
            if(!vis[x] and in[x]) dfs2(x,u);
        }   
        if(p!=-1) ans|=((ll)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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1808 KB Output is correct
2 Correct 4 ms 2128 KB Output is correct
3 Correct 11 ms 2580 KB Output is correct
4 Correct 3 ms 2064 KB Output is correct
5 Correct 5 ms 2064 KB Output is correct
6 Correct 6 ms 2060 KB Output is correct
7 Correct 10 ms 2576 KB Output is correct
8 Correct 9 ms 2576 KB Output is correct
9 Correct 9 ms 2576 KB Output is correct
10 Correct 4 ms 2068 KB Output is correct
11 Correct 8 ms 2512 KB Output is correct
12 Correct 2 ms 1808 KB Output is correct
13 Correct 11 ms 2704 KB Output is correct
14 Correct 10 ms 2616 KB Output is correct
15 Correct 10 ms 2576 KB Output is correct
16 Correct 10 ms 2568 KB Output is correct
17 Correct 11 ms 2580 KB Output is correct
18 Correct 10 ms 2632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 40336 KB Output is correct
2 Correct 371 ms 40844 KB Output is correct
3 Correct 381 ms 40852 KB Output is correct
4 Correct 371 ms 37392 KB Output is correct
5 Correct 369 ms 39268 KB Output is correct
6 Correct 367 ms 38732 KB Output is correct
7 Correct 364 ms 38776 KB Output is correct
8 Correct 384 ms 39044 KB Output is correct
9 Correct 371 ms 39288 KB Output is correct
10 Correct 347 ms 37600 KB Output is correct
11 Correct 338 ms 37540 KB Output is correct
12 Correct 332 ms 34148 KB Output is correct
13 Correct 331 ms 34160 KB Output is correct
14 Correct 364 ms 35792 KB Output is correct
15 Correct 385 ms 37336 KB Output is correct
16 Correct 370 ms 37356 KB Output is correct
17 Correct 380 ms 37744 KB Output is correct
18 Correct 371 ms 37436 KB Output is correct
19 Correct 375 ms 37684 KB Output is correct
20 Correct 335 ms 39368 KB Output is correct
21 Correct 337 ms 38936 KB Output is correct
22 Correct 361 ms 38392 KB Output is correct
23 Correct 370 ms 39104 KB Output is correct
24 Correct 379 ms 38592 KB Output is correct
25 Correct 371 ms 38900 KB Output is correct
26 Correct 377 ms 39332 KB Output is correct
27 Correct 369 ms 39076 KB Output is correct
28 Correct 374 ms 39072 KB Output is correct
29 Correct 338 ms 35468 KB Output is correct
30 Correct 348 ms 37016 KB Output is correct
31 Correct 5 ms 2060 KB Output is correct
32 Correct 6 ms 2132 KB Output is correct
33 Correct 9 ms 2576 KB Output is correct
34 Correct 5 ms 2060 KB Output is correct
35 Correct 3 ms 2068 KB Output is correct
36 Correct 2 ms 1800 KB Output is correct
37 Correct 2 ms 1808 KB Output is correct
38 Correct 2 ms 1804 KB Output is correct
39 Correct 2 ms 1804 KB Output is correct
40 Correct 3 ms 1800 KB Output is correct
41 Correct 3 ms 2056 KB Output is correct
42 Correct 2 ms 1808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1924 KB Output is correct
2 Correct 3 ms 1992 KB Output is correct
3 Correct 3 ms 2056 KB Output is correct
4 Correct 57 ms 7864 KB Output is correct
5 Correct 56 ms 7868 KB Output is correct
6 Correct 55 ms 7968 KB Output is correct
7 Correct 54 ms 7904 KB Output is correct
8 Correct 56 ms 7940 KB Output is correct
9 Correct 334 ms 41012 KB Output is correct
10 Correct 340 ms 41200 KB Output is correct
11 Correct 332 ms 40924 KB Output is correct
12 Correct 2 ms 1808 KB Output is correct
13 Correct 2 ms 1980 KB Output is correct
14 Correct 2 ms 1808 KB Output is correct
15 Correct 2 ms 1800 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 40576 KB Output is correct
2 Correct 374 ms 40980 KB Output is correct
3 Correct 367 ms 40880 KB Output is correct
4 Correct 371 ms 37468 KB Output is correct
5 Correct 365 ms 40380 KB Output is correct
6 Correct 374 ms 39160 KB Output is correct
7 Correct 383 ms 38932 KB Output is correct
8 Correct 367 ms 38352 KB Output is correct
9 Correct 372 ms 38540 KB Output is correct
10 Correct 340 ms 37528 KB Output is correct
11 Correct 339 ms 37596 KB Output is correct
12 Correct 329 ms 34288 KB Output is correct
13 Correct 337 ms 34332 KB Output is correct
14 Correct 356 ms 35704 KB Output is correct
15 Correct 398 ms 37324 KB Output is correct
16 Correct 404 ms 37336 KB Output is correct
17 Correct 367 ms 37636 KB Output is correct
18 Correct 379 ms 37572 KB Output is correct
19 Correct 375 ms 37472 KB Output is correct
20 Correct 349 ms 39588 KB Output is correct
21 Correct 333 ms 38860 KB Output is correct
22 Correct 373 ms 39188 KB Output is correct
23 Correct 367 ms 38720 KB Output is correct
24 Correct 383 ms 38740 KB Output is correct
25 Correct 362 ms 39064 KB Output is correct
26 Correct 383 ms 38856 KB Output is correct
27 Correct 371 ms 39300 KB Output is correct
28 Correct 369 ms 38816 KB Output is correct
29 Correct 338 ms 35576 KB Output is correct
30 Correct 349 ms 37164 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 40420 KB Output is correct
2 Correct 375 ms 40832 KB Output is correct
3 Correct 382 ms 40872 KB Output is correct
4 Correct 375 ms 37344 KB Output is correct
5 Correct 373 ms 40688 KB Output is correct
6 Correct 372 ms 38604 KB Output is correct
7 Correct 380 ms 38416 KB Output is correct
8 Correct 381 ms 39040 KB Output is correct
9 Correct 372 ms 38832 KB Output is correct
10 Correct 352 ms 37500 KB Output is correct
11 Correct 335 ms 37524 KB Output is correct
12 Correct 327 ms 34364 KB Output is correct
13 Correct 333 ms 34196 KB Output is correct
14 Correct 373 ms 35796 KB Output is correct
15 Correct 379 ms 37428 KB Output is correct
16 Correct 391 ms 37340 KB Output is correct
17 Correct 368 ms 37424 KB Output is correct
18 Correct 374 ms 37408 KB Output is correct
19 Correct 380 ms 37388 KB Output is correct
20 Correct 344 ms 39616 KB Output is correct
21 Correct 341 ms 38836 KB Output is correct
22 Correct 374 ms 38984 KB Output is correct
23 Correct 370 ms 38704 KB Output is correct
24 Correct 372 ms 38648 KB Output is correct
25 Correct 371 ms 39000 KB Output is correct
26 Correct 369 ms 38632 KB Output is correct
27 Correct 374 ms 39300 KB Output is correct
28 Correct 365 ms 39340 KB Output is correct
29 Correct 353 ms 35876 KB Output is correct
30 Correct 358 ms 37240 KB Output is correct
31 Correct 5 ms 2068 KB Output is correct
32 Correct 6 ms 2260 KB Output is correct
33 Correct 11 ms 2628 KB Output is correct
34 Correct 4 ms 2068 KB Output is correct
35 Correct 3 ms 2000 KB Output is correct
36 Correct 2 ms 1800 KB Output is correct
37 Correct 2 ms 1808 KB Output is correct
38 Correct 2 ms 1800 KB Output is correct
39 Correct 2 ms 1744 KB Output is correct
40 Correct 2 ms 1808 KB Output is correct
41 Correct 4 ms 2056 KB Output is correct
42 Correct 2 ms 1808 KB Output is correct