Submission #594431

#	Time	Username	Problem	Language	Result	Execution time	Memory
594431		Bench0310	Tropical Garden (IOI11_garden)	C++17	100 / 100	3534 ms	33720 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;
typedef long long ll;

const int N=150000;
const int M=150000;
int p;
array<int,2> opt[N];
int endpoint[2*M];
int to[2*M];
array<int,2> precycle[2*M];
array<int,2> incycle[2*M];
bool partcycle[2*M];
int cyclelen[2*M];
int st[2*M];
vector<int> now;

int one(array<int,2> &a)
{
    int t=0;
    while(t<2&&a[t]!=-1) t++;
    return t;
}

void dfs(int a)
{
    int b=to[a];
    st[a]=1;
    now.push_back(a);
    if(st[b]==1)
    {
        int sz=now.size();
        int pos=sz-1;
        while(now[pos]!=b) pos--;
        int len=sz-pos;
        vector<int> v;
        for(int i=pos;i<sz;i++)
        {
            partcycle[now[i]]=1;
            cyclelen[now[i]]=len;
            if(endpoint[now[i]]==p) v.push_back(i);
        }
        assert(v.size()<=2);
        for(int i=pos;i<sz;i++)
        {
            for(int x:v)
            {
                int t=(((x-i)%len)+len)%len;
                incycle[now[i]][one(incycle[now[i]])]=t;
            }
        }
    }
    else
    {
        if(st[b]==0) dfs(b);
        if(!partcycle[a])
        {
            cyclelen[a]=cyclelen[b];
            for(int i=0;i<2;i++) if(incycle[b][i]!=-1) incycle[a][i]=incycle[b][i]+1;
            for(int i=0;i<2;i++) if(precycle[b][i]!=-1) precycle[a][i]=precycle[b][i]+1;
        }
        if(!partcycle[a]&&endpoint[a]==p) precycle[a][one(precycle[a])]=0;
    }
    st[a]=2;
    now.pop_back();
}

void count_routes(int n,int m,int tp,int r[][2],int q,int g[])
{
    for(int i=0;i<n;i++) opt[i]={-1,-1};
    for(int i=0;i<2*m;i++)
    {
        precycle[i]=incycle[i]={-1,-1};
        cyclelen[i]=-1;
    }
    auto add_edge=[&](int x,int id)
    {
        int t=one(opt[x]);
        if(t<2) opt[x][t]=id;
    };
    for(int i=0;i<m;i++)
    {
        int a=r[i][0],b=r[i][1];
        endpoint[2*i]=b;
        endpoint[2*i+1]=a;
        add_edge(a,2*i);
        add_edge(b,2*i+1);
    }
    for(int i=0;i<2*m;i++)
    {
        int x=endpoint[i];
        to[i]=opt[x][(opt[x][0]/2==i/2&&opt[x][1]!=-1)];
    }
    p=tp;
    for(int i=0;i<2*m;i++) if(st[i]==0) dfs(i);
    for(int i=0;i<q;i++)
    {
        int k=g[i]-1;
        int res=0;
        for(int j=0;j<n;j++)
        {
            bool ok=0;
            int a=opt[j][0];
            for(int t=0;t<2;t++)
            {
                ok|=(precycle[a][t]==k);
                if(incycle[a][t]!=-1) ok|=(k>=incycle[a][t]&&((k-incycle[a][t])%cyclelen[a])==0);
            }
            res+=ok;
        }
        answer(res);
    }
}

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