제출 #867787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867787		HuyQuang_re_Zero	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	0 / 100	9 ms	33624 KiB

garden

#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,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;
            }
        if(x>0) DFS(x);
        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 && incycle[u]==0)
            for(int i=1;i<=student;i++) res[q[i].pos]+=cnt[q[i].k+h[u]];
    }
    void DFS_add(int u,int i)
    {
        heap.push(h[u]-i);
        for(int v:child[u])
            if(incycle[v]==0) DFS_add(v,i);
    }
    void Find_cycle(int u)
    {
        step++;
        vector <int> cycle;
        while(1)
        {
            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) dfs(u),DFS(u);

        for(int i=0;i<cycle.size();i++)
        {
            int u=cycle[i];
            if(V[u]==finish)
            {
                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();
                    }
                    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();
                    }
                    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=_n; 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)];
           // 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);
}
*/

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31