Submission #852280

#	Time	Username	Problem	Language	Result	Execution time	Memory
852280		abcvuitunggio	Tropical Garden (IOI11_garden)	C++17	69 / 100	5073 ms	38228 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
pair <int, int> edge[300001];
int a[300001],mx[150001],mx2[150001],nxt[300001],ch[300001],target[300001],idx[300001],pos[300001],id,cycle[300001],d[300001],cnt[300001],res;
vector <int> ke[300001],ve[300001],tmp;
void dfs(int u, int k){
    cnt[d[u]]+=target[u];
    if (a[u]){
        if (d[u]>=k)
            res+=(!!cnt[d[u]-k]);
        else
            res+=target[ve[idx[u]][(pos[u]+k-d[u])%(ve[idx[u]].size())]];
    }
    for (int v:ke[u]){
        d[v]=d[u]+1;
        dfs(v,k);
    }
    cnt[d[u]]-=target[u];
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    for (int i=0;i<M;i++){
        edge[M-i-1]={R[i][0],R[i][1]};
        edge[M*2-i-1]={R[i][1],R[i][0]};
    }
    memset(mx,-1,sizeof(mx));
    memset(mx2,-1,sizeof(mx2));
    for (int i=0;i<M*2;i++){
        int u=edge[i].first;
        if (mx[u]%M<i%M){
            mx2[u]=mx[u];
            mx[u]=i;
        }
        else if (mx2[u]%M<i%M)
            mx2[u]=i;
    }
    for (int i=0;i<N;i++)
        a[mx[i]]=1;
    for (int i=0;i<M*2;i++){
        int v=edge[i].second;
        if (mx[v]%M==i%M)
            nxt[i]=(mx2[v]==-1?mx[v]:mx2[v]);
        else
            nxt[i]=mx[v];
        target[i]=(v==P);
    }
    for (int i=0;i<M*2;i++){
        if (!ch[i]){
            tmp.clear();
            int u=i;
            while (true){
                u=nxt[u];
                if (ch[u]>1){
                    for (int j:tmp){
                        idx[j]=idx[u];
                        pos[j]=pos[u];
                        ch[j]=2;
                    }
                    break;
                }
                if (ch[u]==1){
                    int p=0;
                    for (int j=0;j<tmp.size();j++)
                        if (tmp[j]==u)
                            p=j;
                    for (int j=p;j<tmp.size();j++){
                        ve[id].push_back(tmp[j]);
                        pos[tmp[j]]=j-p;
                        cycle[tmp[j]]=1;
                    }
                    for (int j:tmp){
                        idx[j]=id;
                        ch[j]=2;
                    }
                    id++;
                    break;
                }
                tmp.push_back(u);
                ch[u]=1;
            }
        }
    }
    for (int i=0;i<M*2;i++)
        if (!cycle[i])
            ke[nxt[i]].push_back(i);
    for (int i=0;i<Q;i++){
        res=0;
        for (int j=0;j<id;j++)
            for (int k:ve[j])
                dfs(k,G[i]-1);
        answer(res);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:64:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |                     for (int j=0;j<tmp.size();j++)
      |                                  ~^~~~~~~~~~~
garden.cpp:67:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                     for (int j=p;j<tmp.size();j++){
      |                                  ~^~~~~~~~~~~

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