oj.uz

Submission #850298

# Submission time Handle Problem Language Result Execution time Memory
850298 2023-09-16T09:42:12 Z alexdd Amusement Park (JOI17_amusement_park) C++17
100 / 100
 28 ms 7628 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
static bool visited[10005];
static bool visited2[10005];
static vector<int> ord;
static vector<int> con[10005];
static bool done[10005];
static int maxd[10005];
static int siz[10005];
static int parent[10005];
static int subtask;
static bool cmp(int x, int y)
{
    if(siz[x]<siz[y])
        return 1;
    if(siz[x]>siz[y])
        return 0;
    if(maxd[x]<maxd[y])
        return 1;
    if(maxd[x]>maxd[y])
        return 0;
    return x<y;
}
static void dfs_init(int nod)
{
    visited2[nod]=1;
    siz[nod]=1;
    maxd[nod]=1;
    for(auto adj:con[nod])
    {
        if(!visited2[adj])
        {
            parent[adj]=nod;
            dfs_init(adj);
            maxd[nod]=max(maxd[nod],maxd[adj]+1);
            siz[nod]+=siz[adj];
        }
    }
}
static void dfs(int nod)
{
    visited[nod]=1;
    sort(con[nod].begin(),con[nod].end(),cmp);
    ord.push_back(nod);
    for(auto adj:con[nod])
    {
        if(!visited[adj])
        {
            dfs(adj);
            ord.push_back(nod);
        }
    }
}
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
    if(T==5 && N>=240)
        T=4;
    subtask=T;
    ord.clear();
    for(int i=0;i<N;i++)
    {
        visited[i]=0;
        visited2[i]=0;
        con[i].clear();
        done[i]=0;
    }

    for(int i=0;i<M;i++)
    {
        con[A[i]].push_back(B[i]);
        con[B[i]].push_back(A[i]);
    }
    if(T!=5)
    {
        dfs_init(0);
        dfs(0);
    }
    else
    {
        for(int root=0;root<N;root++)
        {
            for(int i=0;i<N;i++)
            {
                visited[i]=0;
                visited2[i]=0;
            }
            dfs_init(root);
            dfs(root);
            if(root+1<N)
            {
                vector<int> cv;
                int cur=root+1;
                while(cur!=root)
                {
                    cv.push_back(cur);
                    cur=parent[cur];
                }
                for(int i=cv.size()-1;i>0;i--)
                {
                    ord.push_back(cv[i]);
                }
            }
        }
    }
    int cnt=0;
    for(int i=0;i<(int)ord.size();i++)
    {
        if(!done[ord[i]])
        {
            if(((1LL<<cnt)&X))
                MessageBoard(ord[i],1);
            else
                MessageBoard(ord[i],0);
            cnt=(cnt+1)%60;
            done[ord[i]]=1;
        }
    }
}



#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
static const int INF = 1e9;
static bool visited[10005];
static bool visited2[10005];
static vector<int> ord;
static vector<int> con[10005];
static bool done[10005];
static int p[500005];
static vector<int> poz[10005];
static int fr[65];
static int frst[65];
static int frdr[65];
static int care[10005];
static int maxd[10005];
static int siz[10005];
static int parent[10005];
static int subtask;
static bool cmp(int x, int y)
{
    if(siz[x]<siz[y])
        return 1;
    if(siz[x]>siz[y])
        return 0;
    if(maxd[x]<maxd[y])
        return 1;
    if(maxd[x]>maxd[y])
        return 0;
    return x<y;
}
static void dfs_init(int nod)
{
    visited2[nod]=1;
    siz[nod]=1;
    maxd[nod]=1;
    for(auto adj:con[nod])
    {
        if(!visited2[adj])
        {
            parent[adj]=nod;
            dfs_init(adj);
            maxd[nod]=max(maxd[nod],maxd[adj]+1);
            siz[nod]+=siz[adj];
        }
    }
}
static void dfs(int nod)
{
    visited[nod]=1;
    sort(con[nod].begin(),con[nod].end(),cmp);
    poz[nod].push_back(ord.size());
    ord.push_back(nod);
    for(auto adj:con[nod])
    {
        if(!visited[adj])
        {
            dfs(adj);
            poz[nod].push_back(ord.size());
            ord.push_back(nod);
        }
    }
}
static int calc_moves(int init)
{
    for(int i=0;i<60;i++)
    {
        frst[i]=0;
        frdr[i]=0;
    }
    int cntst=0,cntdr=0,pozst,pozdr;
    for(int i=init;i<(int)ord.size();i++)
    {
        if(frdr[p[i]]==0)
        {
            frdr[p[i]]=1;
            cntdr++;
            if(cntdr==60)
            {
                pozdr=i-init;
                break;
            }
        }
    }
    for(int i=init;i>=0;i--)
    {
        if(frst[p[i]]==0)
        {
            frst[p[i]]=1;
            cntst++;
            if(cntst==60)
            {
                pozst=init-i;
                break;
            }
        }
    }
    if((cntdr==60 && cntst<60) || (cntdr==60 && cntst==60 && pozdr<pozst) || (cntdr<60 && cntst<60 && init>ord.size()-init))
    {
        if(cntdr==60)
            return pozdr;
        return 2*((int)ord.size()-init) + init;
    }
    else
    {
        if(cntst==60)
            return pozst;
        return ((int)ord.size()-init) + 2*init;
    }
}
static long long solve(int init, int V)
{
    for(int i=0;i<60;i++)
    {
        frst[i]=0;
        frdr[i]=0;
        fr[i]=0;
    }
    int cntst=0,cntdr=0,pozst,pozdr;
    for(int i=init;i<(int)ord.size();i++)
    {
        if(frdr[p[i]]==0)
        {
            frdr[p[i]]=1;
            cntdr++;
            if(cntdr==60)
            {
                pozdr=i-init;
                break;
            }
        }
    }
    for(int i=init;i>=0;i--)
    {
        if(frst[p[i]]==0)
        {
            frst[p[i]]=1;
            cntst++;
            if(cntst==60)
            {
                pozst=init-i;
                break;
            }
        }
    }
    long long rez=0;
    int cate=0;
    if((cntdr==60 && cntst<60) || (cntdr==60 && cntst==60 && pozdr<pozst) || (cntdr<60 && cntst<60 && init>ord.size()-init))
    {
        for(int i=init;i<(int)ord.size();i++)
        {
            if(fr[p[i]]==0)
            {
                if(V==1) rez += (1LL<<(p[i]));
                fr[p[i]]=1;
                cate++;
                if(cate==60)
                    return rez;
            }
            if(i+1<(int)ord.size()) V = Move(ord[i+1]);
        }
        for(int i=(int)ord.size()-1;i>=0;i--)
        {
            if(fr[p[i]]==0)
            {
                if(V==1) rez += (1LL<<(p[i]));
                fr[p[i]]=1;
                cate++;
                if(cate==60)
                    return rez;
            }
            V = Move(ord[i-1]);
        }
    }
    else
    {
        for(int i=init;i>=0;i--)
        {
            if(fr[p[i]]==0)
            {
                if(V==1) rez += (1LL<<(p[i]));
                fr[p[i]]=1;
                cate++;
                if(cate==60)
                    return rez;
            }
            if(i-1>=0) V = Move(ord[i-1]);
        }
        for(int i=0;i<(int)ord.size();i++)
        {
            if(fr[p[i]]==0)
            {
                if(V==1) rez += (1LL<<(p[i]));
                fr[p[i]]=1;
                cate++;
                if(cate==60)
                    return rez;
            }
            V = Move(ord[i+1]);
        }
    }
    return rez;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
    if(T==5 && N>=240)
        T=4;
    subtask=T;
    ord.clear();
    for(int i=0;i<N;i++)
    {
        visited[i]=0;
        visited2[i]=0;
        con[i].clear();
        poz[i].clear();
        done[i]=0;
    }

    for(int i=0;i<M;i++)
    {
        con[A[i]].push_back(B[i]);
        con[B[i]].push_back(A[i]);
    }
    if(T!=5)
    {
        dfs_init(0);
        dfs(0);
    }
    else
    {
        for(int root=0;root<N;root++)
        {
            for(int i=0;i<N;i++)
            {
                visited[i]=0;
                visited2[i]=0;
            }
            dfs_init(root);
            dfs(root);
            if(root+1<N)
            {
                vector<int> cv;
                int cur=root+1;
                while(cur!=root)
                {
                    cv.push_back(cur);
                    cur=parent[cur];
                }
                for(int i=cv.size()-1;i>0;i--)
                {
                    poz[cv[i]].push_back(ord.size());
                    ord.push_back(cv[i]);
                }
            }
        }
    }
    int cnt=0;
    for(int i=0;i<(int)ord.size();i++)
    {
        if(!done[ord[i]])
        {
            care[ord[i]]=cnt;
            cnt=(cnt+1)%60;
            done[ord[i]]=1;
        }
        p[i]=care[ord[i]];
        //cout<<i<<" "<<ord[i]<<"  "<<p[i]<<" zzz\n";
    }

    int mnm=INF,idk=-1;
    for(auto x:poz[P])
    {
        int aux = calc_moves(x);
        if(aux<mnm)
        {
            mnm=aux;
            idk=x;
        }
    }
    return solve(idk,V);
}

Compilation message

Ioi.cpp: In function 'int calc_moves(int)':
Ioi.cpp:98:107: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     if((cntdr==60 && cntst<60) || (cntdr==60 && cntst==60 && pozdr<pozst) || (cntdr<60 && cntst<60 && init>ord.size()-init))
      |                                                                                                       ~~~~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int solve(int, int)':
Ioi.cpp:148:107: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     if((cntdr==60 && cntst<60) || (cntdr==60 && cntst==60 && pozdr<pozst) || (cntdr<60 && cntst<60 && init>ord.size()-init))
      |                                                                                                       ~~~~^~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:148:59: warning: 'pozst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |     if((cntdr==60 && cntst<60) || (cntdr==60 && cntst==60 && pozdr<pozst) || (cntdr<60 && cntst<60 && init>ord.size()-init))
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Ioi.cpp:119:25: note: 'pozst' was declared here
  119 |     int cntst=0,cntdr=0,pozst,pozdr;
      |                         ^~~~~
Ioi.cpp:148:59: warning: 'pozdr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |     if((cntdr==60 && cntst<60) || (cntdr==60 && cntst==60 && pozdr<pozst) || (cntdr<60 && cntst<60 && init>ord.size()-init))
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Ioi.cpp:119:31: note: 'pozdr' was declared here
  119 |     int cntst=0,cntdr=0,pozst,pozdr;
      |                               ^~~~~
Ioi.cpp:274:9: warning: 'pozst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  274 |         if(aux<mnm)
      |         ^~
Ioi.cpp:274:9: warning: 'mnm' may be used uninitialized in this function [-Wmaybe-uninitialized]
Ioi.cpp:71:31: warning: 'pozdr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |     int cntst=0,cntdr=0,pozst,pozdr;
      |                               ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3356 KB Output is correct
2 Correct 2 ms 3740 KB Output is correct
3 Correct 2 ms 3428 KB Output is correct
4 Correct 2 ms 3344 KB Output is correct
5 Correct 2 ms 3352 KB Output is correct
6 Correct 2 ms 3352 KB Output is correct
7 Correct 2 ms 3360 KB Output is correct
8 Correct 2 ms 3352 KB Output is correct
9 Correct 2 ms 3360 KB Output is correct
10 Correct 1 ms 3356 KB Output is correct
11 Correct 4 ms 3916 KB Output is correct
12 Correct 2 ms 3596 KB Output is correct
13 Correct 2 ms 3380 KB Output is correct
14 Correct 2 ms 3344 KB Output is correct
15 Correct 2 ms 3352 KB Output is correct
16 Correct 2 ms 3268 KB Output is correct
17 Correct 2 ms 3360 KB Output is correct
18 Correct 2 ms 3352 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7408 KB Output is correct
2 Correct 19 ms 7528 KB Output is correct
3 Correct 20 ms 7528 KB Output is correct
4 Correct 12 ms 5604 KB Output is correct
5 Correct 12 ms 6380 KB Output is correct
6 Correct 12 ms 6116 KB Output is correct
7 Correct 12 ms 6380 KB Output is correct
8 Correct 12 ms 6380 KB Output is correct
9 Correct 13 ms 6372 KB Output is correct
10 Correct 14 ms 5860 KB Output is correct
11 Correct 12 ms 6020 KB Output is correct
12 Correct 10 ms 5588 KB Output is correct
13 Correct 11 ms 5596 KB Output is correct
14 Correct 12 ms 5588 KB Output is correct
15 Correct 18 ms 5592 KB Output is correct
16 Correct 11 ms 5612 KB Output is correct
17 Correct 12 ms 5612 KB Output is correct
18 Correct 13 ms 5584 KB Output is correct
19 Correct 13 ms 5592 KB Output is correct
20 Correct 9 ms 6372 KB Output is correct
21 Correct 12 ms 6548 KB Output is correct
22 Correct 15 ms 6116 KB Output is correct
23 Correct 13 ms 6376 KB Output is correct
24 Correct 12 ms 6284 KB Output is correct
25 Correct 12 ms 6372 KB Output is correct
26 Correct 12 ms 6372 KB Output is correct
27 Correct 11 ms 6376 KB Output is correct
28 Correct 13 ms 6276 KB Output is correct
29 Correct 10 ms 6100 KB Output is correct
30 Correct 14 ms 6320 KB Output is correct
31 Correct 2 ms 3344 KB Output is correct
32 Correct 3 ms 3340 KB Output is correct
33 Correct 2 ms 3344 KB Output is correct
34 Correct 3 ms 3356 KB Output is correct
35 Correct 2 ms 3344 KB Output is correct
36 Correct 2 ms 3348 KB Output is correct
37 Correct 2 ms 3340 KB Output is correct
38 Correct 2 ms 3356 KB Output is correct
39 Correct 2 ms 3348 KB Output is correct
40 Correct 2 ms 3340 KB Output is correct
41 Correct 2 ms 3344 KB Output is correct
42 Correct 2 ms 3356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3356 KB Output is correct
2 Correct 2 ms 3344 KB Output is correct
3 Correct 2 ms 3352 KB Output is correct
4 Correct 3 ms 3896 KB Output is correct
5 Correct 2 ms 3892 KB Output is correct
6 Correct 3 ms 3888 KB Output is correct
7 Correct 2 ms 3888 KB Output is correct
8 Correct 2 ms 3888 KB Output is correct
9 Correct 10 ms 7152 KB Output is correct
10 Correct 10 ms 7140 KB Output is correct
11 Correct 11 ms 7156 KB Output is correct
12 Correct 2 ms 3344 KB Output is correct
13 Correct 2 ms 3344 KB Output is correct
14 Correct 1 ms 3344 KB Output is correct
15 Correct 2 ms 3344 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7540 KB Output is correct
2 Correct 20 ms 7628 KB Output is correct
3 Correct 23 ms 7352 KB Output is correct
4 Correct 12 ms 5600 KB Output is correct
5 Correct 12 ms 6888 KB Output is correct
6 Correct 13 ms 6376 KB Output is correct
7 Correct 13 ms 6404 KB Output is correct
8 Correct 14 ms 6032 KB Output is correct
9 Correct 12 ms 6120 KB Output is correct
10 Correct 14 ms 5864 KB Output is correct
11 Correct 14 ms 5848 KB Output is correct
12 Correct 11 ms 5588 KB Output is correct
13 Correct 12 ms 5588 KB Output is correct
14 Correct 11 ms 5600 KB Output is correct
15 Correct 11 ms 5612 KB Output is correct
16 Correct 11 ms 5604 KB Output is correct
17 Correct 12 ms 5620 KB Output is correct
18 Correct 14 ms 5544 KB Output is correct
19 Correct 12 ms 5604 KB Output is correct
20 Correct 12 ms 6372 KB Output is correct
21 Correct 14 ms 6508 KB Output is correct
22 Correct 15 ms 6372 KB Output is correct
23 Correct 15 ms 6372 KB Output is correct
24 Correct 12 ms 6372 KB Output is correct
25 Correct 13 ms 6368 KB Output is correct
26 Correct 12 ms 6364 KB Output is correct
27 Correct 12 ms 6372 KB Output is correct
28 Correct 14 ms 6116 KB Output is correct
29 Correct 11 ms 6024 KB Output is correct
30 Correct 11 ms 6360 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7512 KB Output is correct
2 Correct 23 ms 7540 KB Output is correct
3 Correct 28 ms 7328 KB Output is correct
4 Correct 12 ms 5604 KB Output is correct
5 Correct 12 ms 7140 KB Output is correct
6 Correct 12 ms 6112 KB Output is correct
7 Correct 13 ms 6128 KB Output is correct
8 Correct 12 ms 6372 KB Output is correct
9 Correct 14 ms 6168 KB Output is correct
10 Correct 15 ms 5864 KB Output is correct
11 Correct 12 ms 5876 KB Output is correct
12 Correct 12 ms 5596 KB Output is correct
13 Correct 12 ms 5592 KB Output is correct
14 Correct 14 ms 5584 KB Output is correct
15 Correct 11 ms 5592 KB Output is correct
16 Correct 13 ms 5604 KB Output is correct
17 Correct 13 ms 6012 KB Output is correct
18 Correct 13 ms 5612 KB Output is correct
19 Correct 12 ms 5608 KB Output is correct
20 Correct 10 ms 6376 KB Output is correct
21 Correct 12 ms 6388 KB Output is correct
22 Correct 13 ms 6380 KB Output is correct
23 Correct 13 ms 6172 KB Output is correct
24 Correct 14 ms 6376 KB Output is correct
25 Correct 14 ms 6372 KB Output is correct
26 Correct 14 ms 6136 KB Output is correct
27 Correct 12 ms 6372 KB Output is correct
28 Correct 13 ms 6544 KB Output is correct
29 Correct 12 ms 6380 KB Output is correct
30 Correct 12 ms 6368 KB Output is correct
31 Correct 3 ms 4500 KB Output is correct
32 Correct 5 ms 4888 KB Output is correct
33 Correct 2 ms 3352 KB Output is correct
34 Correct 4 ms 4248 KB Output is correct
35 Correct 2 ms 3868 KB Output is correct
36 Correct 2 ms 3748 KB Output is correct
37 Correct 2 ms 3608 KB Output is correct
38 Correct 2 ms 3424 KB Output is correct
39 Correct 2 ms 3360 KB Output is correct
40 Correct 2 ms 3872 KB Output is correct
41 Correct 2 ms 3872 KB Output is correct
42 Correct 2 ms 3616 KB Output is correct