oj.uz

Submission #916205

# Submission time Handle Problem Language Result Execution time Memory
916205 2024-01-25T13:15:12 Z Abito Amusement Park (JOI17_amusement_park) C++14
0 / 100
 3000 ms 1372 KB 
#include "Joi.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int NN=1e4+5;
int n,m,r,dis[NN];
vector<int> adj[NN],q;
bool vis[NN];
int bfs(int s){
    vis[s]=true;
    dis[s]=0;
    q.pb(s);
    int mx=0;
    for (int i=0;i<int(q.size());i++){
        int x=q[i];
        mx=max(mx,dis[x]%60);
        for (auto u:adj[x]){
            if (vis[u]) continue;
            dis[u]=dis[x]+1;
            vis[u]=1;
            q.pb(u);
        }
    }return mx;
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
    n=N,m=M;
    for (int i=0;i<m;i++) adj[A[i]].pb(B[i]),adj[B[i]].pb(A[i]);
    for (int i=0;i<n;i++){
        int mx=bfs(i);
        if (mx<59){
            memset(vis,0,sizeof(vis));
            q.clear();
            continue;
        }
        r=i;
        break;
    }
    for (int i=0;i<n;i++) MessageBoard(i,bool(X&(1<<(dis[i]%60))));
    return;
}

#include "Ioi.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int NN=1e4+5;
long long X=0;
int n,m,dis[NN],r,mxd[NN],calc=1;
bool calced[60];
bool vis[NN];
vector<int> adj[NN],q;
int bfs2(int s){
    vis[s]=true;
    dis[s]=0;
    q.pb(s);
    int mx=0;
    for (int i=0;i<int(q.size());i++){
        int x=q[i];
        mx=max(mx,dis[x]%60);
        for (auto u:adj[x]){
            if (vis[u]) continue;
            dis[u]=dis[x]+1;
            vis[u]=1;
            q.pb(u);
        }
    }return mx;
}
int getmxd(int x,int p){
    mxd[x]=dis[x];
    for (auto u:adj[x]) if (u!=p) mxd[x]=max(mxd[x],getmxd(u,x));
    return mxd[x];
}
void dfs(int node,int p){
    vis[node]=true;
    if (calc==60) return;
    for (auto u:adj[node]){
        if (vis[u]) continue;
        int y=Move(u);
        if (!calced[dis[u]%60]){
            calced[dis[u]%60]=1;
            calc++;
        }
        if (y) X|=(1LL<<(dis[u]%60));
        dfs(u,node);
        if (calc==60) return;
    }
    if (p!=-1){
        int y=Move(p);
        if (y) X|=(1LL<<(dis[p]%60));
    }
    return;
}
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<m;i++) adj[A[i]].pb(B[i]),adj[B[i]].pb(A[i]);
    for (int i=0;i<n;i++){
        int mx=bfs2(i);
        if (mx<59){
            memset(vis,0,sizeof(vis));
            q.clear();
            continue;
        }r=i;
        break;
    }if (V) X|=(1LL<<(dis[P]%60));
    memset(vis,0,sizeof(vis));
    calced[dis[P]%60]=1;
    getmxd(r,-1);
    memset(vis,0,sizeof(vis));
    dfs(P,-1);
    return X;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1304 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 3022 ms 1368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1300 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 3058 ms 1372 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 3021 ms 1372 KB Time limit exceeded
2 Halted 0 ms 0 KB -