oj.uz

Submission #709332

# Submission time Handle Problem Language Result Execution time Memory
709332 2023-03-13T11:45:31 Z Antekb Amusement Park (JOI17_amusement_park) C++17
0 / 100
 117 ms 4788 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void debug2(){cerr<<"\n";}
template<typename H, typename... T>
void debug2(H h, T... t){
  cerr<<h;
  if(sizeof...(t))cerr<<", ";
  debug2(t...);
}
#define deb(x) cerr<<#x<<" = ";debug2(x);
mt19937 rng2(chrono::high_resolution_clock().now().time_since_epoch().count());
const int NN2=1e4+5;
#include "Joi.h"

vector<int> bit2;
vi E2[NN2];
int reszta2;
int vis2[NN2], czy2[NN2], kol2[NN2];
vector<pii> todo2;
int ddfs2(int v){
    int m=0;
    vis2[v]=2;
    for(int u:E2[v]){
        if(czy2[u] && vis2[u]!=2){
            m=max(m, ddfs2(u));
        }
    }
    m++;
    todo2.eb(-m, v);
    return m;
}
int ddfs(int v){
    int sz=0;
    vis2[v]=1;
    for(int u:E2[v]){
        if(!vis2[u]){
            sz+=ddfs(u);
        }
    }
    czy2[v]=1;
    sz++;
    if(v==0 || (reszta2>=120 && sz>=60)){
        ddfs2(v);
        sort(all(todo2));
        for(int i=0; i<60; i++)kol2[todo2[i].nd]=i;
        for(pii i:todo2)czy2[i.nd]=0;
        sz=0;
        reszta2-=todo2.size();
        todo2.clear();
    }
    return sz;
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
    reszta2=n;
    for(int i=0; i<m; i++){
        E2[A[i]].pb(B[i]);
        E2[B[i]].pb(A[i]);
    }
    for(int i=0; i<60; i++)bit2.pb(X&1), X/=2;
    ddfs(0);
    for(int i=0; i<n; i++){
        MessageBoard(i, bit2[kol2[i]]);
    }
}

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
  cerr<<h;
  if(sizeof...(t))cerr<<", ";
  debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const int NN=1e4+5, INF=1e9+5;
#include "Ioi.h"

int bit[60];
int reszta;
vi E[NN];
int vis[NN], czy[NN], kol[NN], par[NN];
vector<pii> todo;
int pp;
int dfs2(int v){
    int m=0;
    vis[v]=2;
    for(int u:E[v]){
        if(czy[u] && vis[u]!=2){
            m=max(m, dfs2(u));
        }
    }
    m++;
    todo.eb(-m, v);
    return m;
}
void move(int x){
    int t=Move(x);
    bit[kol[x]]=t;
}
void dfs3(int v){
    vis[v]=2;
    for(int u:E[v]){
        if(vis[u]==3){
            move(u);
            dfs3(u);
            move(v);
        }
    }
}
int dfs(int v){
    int sz=0;
    vis[v]=1;
    for(int u:E[v]){
        if(!vis[u]){
            par[u]=v;
            sz+=dfs(u);
        }
    }
    czy[v]=1;
    deb(v, 1);
    sz++;
    if(v==0 || (reszta>=120 && sz>=60)){
        deb(v);
        dfs2(v);
        sort(all(todo));
        for(int i=0; i<60; i++)kol[todo[i].nd]=i, vis[todo[i].nd]=3;
        if(czy[pp]){
            deb(v);
            while(vis[pp]!=3)move(par[pp]), pp=par[pp];
            dfs3(pp);
        }
        for(pii i:todo)czy[i.nd]=0;
        sz=0;
        reszta-=todo.size();
        todo.clear();
    }
    return sz;
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    reszta=n;
    for(int i=0; i<m; i++){
        E[A[i]].pb(B[i]);
        E[B[i]].pb(A[i]);
    }
    pp=P;
    dfs(0);
    bit[kol[P]]=V;
    ll x=0;
    for(int i=59; i>=0; i--)x=x+x+bit[i];
    return x;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1216 KB Output is correct
2 Correct 3 ms 1028 KB Output is correct
3 Correct 5 ms 1300 KB Output is correct
4 Correct 2 ms 1144 KB Output is correct
5 Correct 2 ms 1028 KB Output is correct
6 Correct 3 ms 1156 KB Output is correct
7 Correct 4 ms 1288 KB Output is correct
8 Correct 4 ms 1240 KB Output is correct
9 Correct 4 ms 1288 KB Output is correct
10 Incorrect 3 ms 1036 KB Wrong Answer [7]
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 4740 KB Output is correct
2 Correct 112 ms 4756 KB Output is correct
3 Correct 98 ms 4788 KB Output is correct
4 Incorrect 60 ms 3016 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 3 ms 1108 KB Output is correct
4 Correct 16 ms 1580 KB Output is correct
5 Incorrect 20 ms 1580 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 4772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 4652 KB Output isn't correct
2 Halted 0 ms 0 KB -