Submission #543425

#	Time	Username	Problem	Language	Result	Execution time	Memory
543425		ogibogi2004	Tropical Garden (IOI11_garden)	C++14	0 / 100	5 ms	9172 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=15e4+6;
const int INF=1e9;
bool ending[2*MAXN];
int nxt[2*MAXN];
vector<pair<int,int> >edges;
vector<pair<int,int> >g[MAXN];
int dist[2*MAXN];
int which[2*MAXN];
vector<int>rev[MAXN];
int cnt[3*MAXN];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    for(int i=0;i<M;i++)
    {
        R[i][0]++;
        R[i][1]++;
    }
    //for(int i=0;i<Q;i++)G[i]++;
    P++;
    for(int i=0;i<M;i++)
    {
        if(R[i][1]==P)
        {
            //cout<<" - "<<2*i<<endl;
            ending[2*i]=1;
        }
        edges.push_back({R[i][0],R[i][1]});
        if(R[i][0]==P)
        {
            //cout<<" - "<<2*i+1<<endl;
            ending[2*i+1]=1;
        }
        edges.push_back({R[i][1],R[i][0]});

        g[R[i][0]].push_back({R[i][1],2*i});
        g[R[i][1]].push_back({R[i][0],2*i+1});
    }
    for(int i=0;i<edges.size();i++)
    {
        if(g[edges[i].second].size()==1)
        {
            nxt[i]=g[edges[i].second][0].second;
        }
        else if(g[edges[i].second][0].first==edges[i].first)
        {
            nxt[i]=g[edges[i].second][1].second;
        }
        else
        {
            nxt[i]=g[edges[i].second][0].second;
        }
        rev[nxt[i]].push_back(i);
    }
    queue<int>q;
    for(int i=0;i<edges.size();i++)
    {
        dist[i]=INF;
        if(ending[i]==1)
        {
            //cout<<" "<<i<<endl;
            q.push(i);
            dist[i]=1;
            which[i]=i;
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(auto xd:rev[u])
        {
            if(dist[xd]!=INF)continue;
            dist[xd]=dist[u]+1;
            which[xd]=which[u];
            q.push(xd);
        }
    }
    int cycle_size=-1;
    for(int i=0;i<edges.size();i++)
    {
        if(dist[i]==1)
        {
            //cout<<edges[i].first<<" "<<edges[i].second<<" "<<dist[i]<<endl;
            if(dist[nxt[i]]==INF)continue;
            cycle_size=dist[nxt[i]]+1;
        }
    }
    for(int i=1;i<=N;i++)
    {
        int e=g[i][0].second;
        if(dist[e]!=INF)
        {
            cnt[dist[e]]++;
        }
    }
    if(cycle_size!=-1)for(int i=cycle_size;i<3*MAXN;i++)cnt[i]+=cnt[i-cycle_size];
    for(int i=0;i<Q;i++)
    {
        if(G[i]<3*MAXN)answer(cnt[G[i]]);
        else if(cycle_size==-1)answer(0);
        else
        {
            int k=(G[i]-3*MAXN)/cycle_size+1;
            k=G[i]-k*cycle_size;
            answer(cnt[k]);
        }
    }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<edges.size();i++)
      |                 ~^~~~~~~~~~~~~
garden.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<edges.size();i++)
      |                 ~^~~~~~~~~~~~~
garden.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<edges.size();i++)
      |                 ~^~~~~~~~~~~~~

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