제출 #895256

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

garden

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

using namespace std;
#define pii pair<int, int>

const int MAX_N = 2*1e5;
int bl[2*MAX_N][30];

int max_p[MAX_N];
vector<vector<pii>> adj;

int target;
int n;

int dfs(int u, vector<int>& vis, int d){
    ////////cout<<"dfs "<<u<<" "<<u%n<<" "<<u/n<<endl;
    vis[u] =d;
    if(vis[bl[u][0]] == -1){
        return dfs(bl[u][0], vis, d+1);
    }
    else{
        if(bl[u][0] == target){
            return d+1;
        }
        else{
            return -1;
        }
    }
}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n =N;
    adj.resize(N);
    for(int i = 0; i <M; i++){
        adj[R[i][0]].push_back(pii(i, R[i][1]));
        adj[R[i][1]].push_back(pii(i, R[i][0]));

    }
    for(int i = 0; i<N; i++){
        max_p[i] = adj[i][0].first;
    }
  for(int i = 0; i<N; i++){
    bl[i][0] = adj[i][0].second;
    if(adj[i][0].first == max_p[adj[i][0].second]){
        bl[i][0] += N;
    }
    if(adj[i].size()>1){
        bl[i+N][0] = adj[i][1].second;
        if(adj[i][1].first == max_p[adj[i][1].second]){
            bl[i+N][0] += N;
        }
    }
    else{
        bl[i+N][0] = bl[i][0];
    }
  }

  for(int step = 1; step<30; step++){
    for(int i = 0; i<2*N; i++){
        bl[i][step] = bl[bl[i][step-1]][step-1];
    }
  }

  vector<int> res(Q, 0);

  auto calc = [&](){
    vector<int> ch(2*N, -1);
    int len = dfs(target, ch, 0);
    ////////cout<<endl;
    //cout<<len<<endl;
    if(len == -1){
        map<int, int> oc;
        for(int i = 0; i<N; i++){
        
            int dist= -1;
            if(i == target){
                dist = 0;
            }
            else if(ch[i]!=-1){
                dist= -1;
            }
            else{
                int cur = i;
                dist = 1;
                for(int step = 29; step>=0; step--){
                    if(ch[bl[cur][step]] == -1){
                        cur = bl[cur][step];
                        dist+= (1<<step);
                    }
                    ////cout<<dist<<endl;
                }

                if(bl[cur][0] == target){
                    
                }
                else{
                    dist = -1;
                }
            }
            //cout<<i<<"dist "<<dist<<endl;

            if(dist!=-1){
                oc[dist] ++;
            }
        }
        for(int i = 0; i<Q; i++){

            res[i] += oc[G[i]]; 
            
        }
    }
    else{
        vector<vector<int>> oc(len);
        for(int i = 0; i<N; i++){
            int dist= -1;
            if(i == target){
                dist = 0;
            }
            else if(ch[i]!=-1){
                dist= len-ch[i];
            }
            else{
                int cur = i;
                dist = 1;
                for(int step = 29; step>=0; step--){
                    if(ch[bl[cur][step]] == -1){
                        cur = bl[cur][step];
                        dist+=(1<<step);
                    }
                }


                if(ch[bl[cur][0]] != -1){
                    dist += (len-ch[bl[cur][0]])%len;
                }
                else{
                    dist = -1;
                }
            }
            if(dist!=-1){
                oc[dist%len].push_back(dist);
            }

            //cout<<i<<" dist: "<<dist<<endl;
        
        }

        for(vector<int>& e: oc){
            sort(e.begin(), e.end());
        }

        for(int i = 0; i<Q; i++){
            int mod = G[i]%len;

            for(auto e: oc[mod]){
                //cout<<e<<" | ";
            }
            //cout<<endl;

            int cur =-1;
            for(int step = (1<<29); step>0; step/=2){
                if(cur+step< oc[mod].size() && oc[mod][cur+step]<=G[i]){
                    ////cout<<oc[mod][cur+step]<<endl;
                    cur+=step;
                }
            }
            //cout<<i<<" "<<cur<<" "<<endl;
            res[i]+=cur+1;
        }
        
    }
  };

  target = P;
  calc();
  target = P+N;
  calc();

  for(auto e: res){
    answer(e);
  }
}

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

garden.cpp: In lambda function:
garden.cpp:159:22: warning: unused variable 'e' [-Wunused-variable]
  159 |             for(auto e: oc[mod]){
      |                      ^
garden.cpp:166:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |                 if(cur+step< oc[mod].size() && oc[mod][cur+step]<=G[i]){
      |                    ~~~~~~~~^~~~~~~~~~~~~~~~

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