oj.uz

Submission #730920

# Submission time Handle Problem Language Result Execution time Memory
730920 2023-04-26T15:42:32 Z Rafi22 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 726 ms 202640 KB 
#include <bits/stdc++.h>
#include "Joi.h"
 
using namespace std;
 
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
static ll mod=1000000007;
static int inf=1000000007;
static ll infl=1000000000000000007;
 
static const int N=10007;
 
static bool odw[N];
static vector<int>G[N],G1[N];
static vector<int>X[N];
static int id[N];
 
static vector<int>V;
 
static void dfs(int v)
{
    if(sz(V)<60)
    {
        id[v]=sz(V);
        V.pb(v);
    }
    odw[v]=1;
    for(auto u:G[v])
    {
        if(!odw[u])
        {
            G1[u].pb(v);
            G1[v].pb(u);
            dfs(u);
        }
    }
}
 
static bool is[N];
 
static void dfs1(int v,int o)
{
    for(auto u:G1[v])
    {
        if(u==o) continue;
        if(sz(X[u])==0)
        {
            int l=-1;
            for(auto i:X[v]) is[i]=1;
            for(auto i:X[v])
            {
                int c=0;
                for(auto j:G1[i]) c+=is[j];
                if(c==1) l=i;
            }
            id[u]=id[l];
            for(auto i:X[v])
            {
                is[i]=0;
                if(i!=l) X[u].pb(i);
            }
            X[u].pb(u);
        }
        dfs1(u,v);
    }
}
 
 
void Joi(int n, int m, int A[], int B[], ll x, int tt)
{
    for(int i=0;i<m;i++)
    {
        G[A[i]].pb(B[i]);
        G[B[i]].pb(A[i]);
    }
    dfs(0);
    for(auto x:V) X[x]=V;
    dfs1(0,-1);
    for(int i=0;i<n;i++) MessageBoard(i,((1LL<<id[i])&x)>0);
}
#include <bits/stdc++.h>
#include "Ioi.h"
 
using namespace std;
 
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
static ll mod=1000000007;
static int inf=1000000007;
static ll infl=1000000000000000007;

 
const static int N=10007;
 
static bool odw[N];
static vector<int>G[N],G1[N];
static vector<int>X[N];
static int id[N];
 
static vector<int>V;
 
static void dfs(int v)
{
    if(sz(V)<60)
    {
        id[v]=sz(V);
        V.pb(v);
    }
    odw[v]=1;
    for(auto u:G[v])
    {
        if(!odw[u])
        {
            G1[u].pb(v);
            G1[v].pb(u);
            dfs(u);
        }
    }
}
 
static bool is[N];
 
static void dfs1(int v,int o)
{
    for(auto u:G1[v])
    {
        if(u==o) continue;
        if(sz(X[u])==0)
        {
            int l=-1;
            for(auto i:X[v]) is[i]=1;
            for(auto i:X[v])
            {
                int c=0;
                for(auto j:G1[i]) c+=is[j];
                if(c==1) l=i;
            }
            id[u]=id[l];
            for(auto i:X[v])
            {
                is[i]=0;
                if(i!=l) X[u].pb(i);
            }
            X[u].pb(u);
        }
        dfs1(u,v);
    }
}
 
static ll ans=0;
 
static void dfs2(int v,int o)
{
    for(auto u:G1[v])
    {
        if(u==o||!is[u]) continue;
        ll x=Move(u);
        ans+=x*(1LL<<id[u]);
        dfs2(u,v);
    }
    if(o!=-1) Move(o);
}
 
ll Ioi(int n, int m, int A[], int B[], int p, int v, int t)
{
    for(int i=0;i<m;i++)
    {
        G[A[i]].pb(B[i]);
        G[B[i]].pb(A[i]);
    }
    dfs(0);
    for(auto x:V) X[x]=V;
    dfs1(0,-1);
    ans+=(ll)v*(1LL<<id[p]);
    for(auto i:X[p]) is[i]=1;
    dfs2(p,-1);
    return ans;
}

Compilation message

Joi.cpp:15:11: warning: 'infl' defined but not used [-Wunused-variable]
   15 | static ll infl=1000000000000000007;
      |           ^~~~
Joi.cpp:14:12: warning: 'inf' defined but not used [-Wunused-variable]
   14 | static int inf=1000000007;
      |            ^~~
Joi.cpp:13:11: warning: 'mod' defined but not used [-Wunused-variable]
   13 | static ll mod=1000000007;
      |           ^~~

Ioi.cpp:15:11: warning: 'infl' defined but not used [-Wunused-variable]
   15 | static ll infl=1000000000000000007;
      |           ^~~~
Ioi.cpp:14:12: warning: 'inf' defined but not used [-Wunused-variable]
   14 | static int inf=1000000007;
      |            ^~~
Ioi.cpp:13:11: warning: 'mod' defined but not used [-Wunused-variable]
   13 | static ll mod=1000000007;
      |           ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2048 KB Output is correct
2 Incorrect 2 ms 2056 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2008 KB Output is correct
2 Correct 3 ms 2056 KB Output is correct
3 Incorrect 2 ms 2056 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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