oj.uz

Submission #867840

# Submission time Handle Problem Language Result Execution time Memory
867840 2023-10-29T14:53:44 Z HuyQuang_re_Zero Tropical Garden (IOI11_garden) C++14
100 / 100
 165 ms 57240 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define mxn 300005
#include "garden.h"
#include "gardenlib.h"
//#define answer(x) cout<<x<<'\n';
using namespace std;
struct International_Olympiad_in_Informatics
{
    priority_queue <int,vector <int>,greater <int> > heap;
    vector <int> a[mxn],child[mxn],changed,in4[mxn];
    int n,m,d[mxn],incycle[mxn],sz[mxn],h[mxn],cnt[mxn],finish,student,U[mxn],V[mxn],res[mxn],step,Turn[mxn],nxt[mxn],i,w[mxn],u,v;
    struct query { int k,pos; } q[mxn];
    void dfs(int u)
    {
        sz[u]=1;
        for(int v:child[u])
            if(incycle[v]==0) h[v]=h[u]+1,dfs(v),sz[u]+=sz[v];
    }
    int rev(int u) { return (u<=m) ? u+m : u-m; }
    void DFS(int u)
    {
        int x=0;
        for(int v:child[u])
            if(incycle[v]==0 && sz[x]<sz[v]) x=v;
        for(int v:child[u])
            if(incycle[v]==0 && v!=x)
            {
                DFS(v);
                in4[v]=changed;
                for(int x:changed) cnt[x]=0;
                changed.clear();
            }
        if(x>0) DFS(x);
        if(d[u]) cnt[h[u]]++,changed.push_back(h[u]);
        for(int v:child[u])
            if(incycle[v]==0 && v!=x)
                for(int x:in4[v]) cnt[x]++,changed.push_back(x);
     //   if(V[u]==finish) cerr<<U[u]<<" "<<V[u]<<'\n';
        if(V[u]==finish && incycle[u]==0)
        {
         //   cerr<<u<<'\n';
            for(int i=1;i<=student;i++)
                if(q[i].k+h[u]<=2*m) res[q[i].pos]+=cnt[q[i].k+h[u]];
        }
    }
    void DFS_add(int u,int i)
    {
        if(d[u]) heap.push(h[u]-i);
        for(int v:child[u])
            if(incycle[v]==0) DFS_add(v,i);
    }
    void Find_cycle(int u)
    {
        step++;
       // cerr<<U[u]<<" "<<V[u]<<'\n';
        vector <int> cycle;
        while(1)
        {
         //   cerr<<u<<'\n';
            Turn[u]=step;
            int v=nxt[u];
            if(Turn[v]==0) u=v;
            else if(Turn[v]<step) return ;
            else
            {
                while(v!=u) cycle.push_back(v),v=nxt[v];
                cycle.push_back(u);
                break;
            }
        }
       for(int u:cycle) incycle[u]=1;
        for(int u:cycle)
        {
            for(int x:changed) cnt[x]=0;
            changed.clear();
            dfs(u),DFS(u);
        }
        for(int i=0;i<cycle.size();i++)
        {
            int u=cycle[i];
            if(V[u]==finish)
            {

              // cerr<<U[u]<<" "<<V[u]<<'\n';
                memset(cnt,0,sizeof(cnt));
                while(heap.size()>0) heap.pop();
                for(int j=0;j<=i;j++) DFS_add(cycle[j],j);
                for(int inq=1;inq<=student;inq++)
                {
                    while(heap.size()>0 && i+heap.top()<=q[inq].k)
                    {
                        cnt[(i+heap.top())%cycle.size()]++;
                        heap.pop();
                    }
                 //   cerr<<cnt[q[inq].k%cycle.size()]<<'\n';
                    res[q[inq].pos]+=cnt[q[inq].k%cycle.size()];
                }

                memset(cnt,0,sizeof(cnt));
                while(heap.size()>0) heap.pop();
                for(int j=(int)cycle.size()-1;j>i;j--) DFS_add(cycle[j],j);
                for(int inq=1;inq<=student;inq++)
                {
                    while(heap.size()>0 && i+cycle.size()+heap.top()<=q[inq].k)
                    {
                        cnt[(i+cycle.size()+heap.top())%cycle.size()]++;
                        heap.pop();
                    }
                    // cerr<<cnt[q[inq].k%cycle.size()]<<'\n';
                    res[q[inq].pos]+=cnt[q[inq].k%cycle.size()];
                }
            }
        }
    }
    void Work(int _n,int _m,int _p,int _r[][2],int _q,int _g[])
    {
        n=_n; m=_m; finish=_p; student=_q;
        for(i=1;i<=m;i++) U[i]=_r[i][0],V[i]=_r[i][1];
        for(i=1;i<=student;i++) _g[i]--,q[i]={ _g[i],i };
        sort(q+1,q+student+1,[&](query a,query b){ return a.k<b.k; });
        /////////////////////////////////////////////////////////////////////////

        for(i=1;i<=m;i++)
        {
            w[i]=i;
            a[U[i]].push_back(i); a[V[i]].push_back(i+m);
            V[i+m]=U[i]; U[i+m]=V[i]; w[i+m]=w[i];
        }

        for(u=1;u<=n;u++) sort(a[u].begin(),a[u].end(),[&](int i,int j){ return w[i]<w[j]; });
        for(i=1;i<=2*m;i++)
        {
            u=U[i]; v=V[i];
            if(a[v].size()==1) nxt[i]=rev(i);
            else nxt[i]=a[v][a[v][0]==rev(i)];
            d[i]=(a[u][0]==i);
         //   if(a[v].size()==1) cerr<<v<<'\n';
         //   cerr<<i<<" "<<nxt[i]<<'\n';
         //   if(V[i]==finish) cerr<<i<<'\n';
        }
        for(u=1;u<=2*m;u++) child[nxt[u]].push_back(u);

        for(u=1;u<=2*m;u++)
            if(Turn[u]==0) Find_cycle(u);
    }
} IOI;
/*
Write a procedure count_routes(N,M,P,R,Q,G) that takes the following parameters:

N – the number of fountains. The fountains are numbered 0 through N-1.
• M– the number of trails. The trails are numbered 0 through M-1. The trails will be given
in decreasing order of beauty: for 0 ≤ i < M-1, trail i is more beautiful than trail i+1.
• P – the fountain at which the premium restaurant is located.
• R – a two-dimensional array representing the trails. For 0 ≤ i < M, trail i connects the
fountains R[i][0] and R[i][1]. Recall that each trail joins a pair of distinct fountains, and
no two trails join the same pair of fountains.
• Q – the number of groups of students.
• G – a one-dimensional array of integers containing the values of K. For 0 ≤ i < Q, G[i] is
the number of trails K that the i-th group will take. */
void count_routes(int n,int m,int p,int r[][2],int q,int g[])
{
    p++;
    for(int i=m;i>=1;i--) r[i][0]=r[i-1][0],r[i][1]=r[i-1][1],r[i][0]++,r[i][1]++;
    for(int i=q;i>=1;i--) g[i]=g[i-1];
    IOI.Work(n,m,p,r,q,g);
    for(int i=0;i<q;i++) answer(IOI.res[i+1]);
}
/*
int n,m,p,i,r[mxn][2],g[mxn],q;
int main()
{
    freopen("garden.inp","r",stdin);
    freopen("garden.out","w",stdout);
    cin>>n>>m>>p;
    for(i=0;i<m;i++) cin>>r[i][0]>>r[i][1];
    cin>>q;
    for(i=0;i<q;i++) cin>>g[i];
    count_routes(n,m,p,r,q,g);
}*/

Compilation message

garden.cpp: In member function 'void International_Olympiad_in_Informatics::Find_cycle(int)':
garden.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int i=0;i<cycle.size();i++)
      |                     ~^~~~~~~~~~~~~
garden.cpp:115:69: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |                     while(heap.size()>0 && i+cycle.size()+heap.top()<=q[inq].k)
      |                                            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35672 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 6 ms 35420 KB Output is correct
6 Correct 7 ms 35840 KB Output is correct
7 Correct 7 ms 35420 KB Output is correct
8 Correct 7 ms 35416 KB Output is correct
9 Correct 10 ms 35676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35672 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 6 ms 35420 KB Output is correct
6 Correct 7 ms 35840 KB Output is correct
7 Correct 7 ms 35420 KB Output is correct
8 Correct 7 ms 35416 KB Output is correct
9 Correct 10 ms 35676 KB Output is correct
10 Correct 7 ms 35420 KB Output is correct
11 Correct 16 ms 37800 KB Output is correct
12 Correct 35 ms 40340 KB Output is correct
13 Correct 51 ms 46184 KB Output is correct
14 Correct 121 ms 55452 KB Output is correct
15 Correct 161 ms 56552 KB Output is correct
16 Correct 122 ms 51400 KB Output is correct
17 Correct 122 ms 51240 KB Output is correct
18 Correct 37 ms 38748 KB Output is correct
19 Correct 129 ms 55284 KB Output is correct
20 Correct 159 ms 56444 KB Output is correct
21 Correct 141 ms 51996 KB Output is correct
22 Correct 125 ms 50816 KB Output is correct
23 Correct 115 ms 55380 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35672 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 6 ms 35420 KB Output is correct
6 Correct 7 ms 35840 KB Output is correct
7 Correct 7 ms 35420 KB Output is correct
8 Correct 7 ms 35416 KB Output is correct
9 Correct 10 ms 35676 KB Output is correct
10 Correct 7 ms 35420 KB Output is correct
11 Correct 16 ms 37800 KB Output is correct
12 Correct 35 ms 40340 KB Output is correct
13 Correct 51 ms 46184 KB Output is correct
14 Correct 121 ms 55452 KB Output is correct
15 Correct 161 ms 56552 KB Output is correct
16 Correct 122 ms 51400 KB Output is correct
17 Correct 122 ms 51240 KB Output is correct
18 Correct 37 ms 38748 KB Output is correct
19 Correct 129 ms 55284 KB Output is correct
20 Correct 159 ms 56444 KB Output is correct
21 Correct 141 ms 51996 KB Output is correct
22 Correct 125 ms 50816 KB Output is correct
23 Correct 115 ms 55380 KB Output is correct
24 Correct 7 ms 35416 KB Output is correct
25 Correct 16 ms 37720 KB Output is correct
26 Correct 37 ms 40440 KB Output is correct
27 Correct 50 ms 46280 KB Output is correct
28 Correct 121 ms 55128 KB Output is correct
29 Correct 161 ms 56460 KB Output is correct
30 Correct 120 ms 51392 KB Output is correct
31 Correct 139 ms 51160 KB Output is correct
32 Correct 38 ms 40448 KB Output is correct
33 Correct 133 ms 55264 KB Output is correct
34 Correct 165 ms 56528 KB Output is correct
35 Correct 136 ms 52048 KB Output is correct
36 Correct 151 ms 51664 KB Output is correct
37 Correct 126 ms 55376 KB Output is correct
38 Correct 133 ms 57240 KB Output is correct