제출 #852308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852308		abcvuitunggio	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	69 / 100	5102 ms	36948 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
pair <int, int> edge[300001];
int a[300001],b[300001],mx[150001],mx2[150001],nxt[300001],ch[300001],t[300001],id,cycle[300001],d[300001],cnt[300001],res;
vector <int> ke[300001],ve[300001],tmp;
void dfs(int u, int i){
    ch[i]|=t[u];
    b[u]=a[u];
    for (int v:ke[u]){
        d[v]=d[u]+1;
        dfs(v,i);
        b[u]|=b[v];
    }
}
void dfs2(int u, int k, int i, int p, int sz){
    if (!b[u])
        return;
    cnt[d[u]]+=t[u];
    if (a[u]){
        if (d[u]>=k)
            res+=(!!cnt[d[u]-k]);
        else
            res+=t[ve[i][(p+k-d[u])%sz]];
    }
    for (int v:ke[u])
        dfs2(v,k,i,p,sz);
    cnt[d[u]]-=t[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];
        t[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)
                        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]);
                        cycle[tmp[j]]=1;
                    }
                    for (int j:tmp)
                        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<id;i++){
        ch[i]=0;
        for (int j:ve[i])
            dfs(j,i);
    }
    for (int i=0;i<Q;i++){
        res=0;
        for (int j=0;j<id;j++)
            if (ch[j])
                for (int k=0;k<ve[j].size();k++)
                    dfs2(ve[j][k],G[i]-1,j,k,ve[j].size());
        answer(res);
    }
}

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

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

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