제출 #316941

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

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=3e5+5;
pair<int,int> e[MX];
int b[MX];
int c[MX];
int nxt[MX];
pair<int,int> d[MX];
int visit[MX];
int ans[MX];
int p;
vector<int> dd[MX];
pair<int,int> f(int k){
    if(d[k].first>=0)return d[k];
    int u=e[k].first;
    int v=e[k].second;
    if(v==p)return {1,k};

    auto ret=f(nxt[k]);
    return d[k]={ret.first+1,ret.second};
}
void dfs(int v){
    visit[v]=1;
    for(auto u: dd[v]){
        if(!visit[u])dfs(u);
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    p=P;
    int i,j;
    for(i=0 ; i<N ; i++)b[i]=c[i]=-1;
    for(i=0 ; i<M ; i++){
        int u=R[i][0];
        int v=R[i][1];
        e[i]={u,v};
        e[M+i]={v,u};
        if(b[u]==-1)b[u]=i;
        else if(c[u]==-1)c[u]=i;
        if(b[v]==-1)b[v]=M+i;
        else if(c[v]==-1)c[v]=M+i;
    }

    for(i=0 ; i<M*2 ; i++){
        int u=e[i].first;
        int v=e[i].second;
        int k=b[v];
        int t=c[v];
        if(t==-1){
            nxt[i]=k;
            dd[k].push_back(i);
            continue;
        }
        if(e[k].second==u){
            nxt[i]=t;
            dd[t].push_back(i);
        }
        else {
            nxt[i]=k;
            dd[k].push_back(i);
        }
    }

    for(i=0 ; i<M*2 ; i++){
        if(e[i].second==P)dfs(i);
    }
    for(i=0 ; i<M*2 ;i++)d[i]={-1,-1};
    for(i=0  ;i<M*2 ; i++){
      ///  cout<<e[i].first<<" "<<e[i].second<<" "<<visit[i]<<endl;
        if(visit[i]==1)d[i]=f(i);
    }

    for(i=0 ; i<N ; i++){
        int k=b[i];
        int w=-1,e=-1,r=-1;
        if(k>=0 && visit[k])
            w=nxt[d[k].second];
        if(w>=0 && visit[w])
            e=nxt[d[w].second];
        if(e>=0 && visit[e])
            r=nxt[d[e].second];

        if(w==-1)continue;
        for(j=0 ; j<Q ; j++){

            if(G[j]<d[k].first)continue;
            if(G[j]==d[k].first){
                ans[j]++;
                continue;
            }
            if(w==e && e>=0){
                if((G[j]-d[k].first)%d[w].first==0)ans[j]++;
            }
            else{
                if(e<0 )continue;
                if(G[j]<d[k].first+d[w].first)continue;
                if(G[j]==d[k].first+d[w].first){
                    ans[j]++;
                    continue;
                }
                if(r<0)continue;
                if(e==r){
                    if((G[j]-d[k].first-d[w].first)%d[e].first==0)ans[j]++;
                }
                else{
                    if((G[j]-d[k].first)%(d[w].first+d[e].first)==0 || (G[j]-d[k].first)%(d[w].first+d[e].first)==d[w].first)ans[j]++;
                }
            }
        }
    }
    for(i=0 ; i<Q ; i++)
        answer(ans[i]);
}

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

garden.cpp: In function 'std::pair<int, int> f(int)':
garden.cpp:17:9: warning: unused variable 'u' [-Wunused-variable]
   17 |     int u=e[k].first;
      |         ^

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