oj.uz

답안 #895211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895211 2023-12-29T15:50:13 Z anton 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 1 ms 4444 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>

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

const int INF = 1e9+1;
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);

  auto calc = [&](){
    vector<int> ch(2*N, -1);
    int len = dfs(target, ch, 0);
    for(auto e:ch){
        //cout<<e<<" ";
    }
    //cout<<endl;
    //cout<<len<<endl;
    if(len == -1){
        map<int, int> oc;
        for(int i = 0; i<N; i++){
            
            if(adj[i%N].size()>1 || i<N){
                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);
                        }
                    }

                    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++){
            if(G[i]<2*N){
               res[i] += oc[G[i]]; 
            }
        }
    }
    else{
        vector<vector<int>> oc(len);
        for(int i = 0; i<N; i++){
            if(adj[i%N].size()>1 || i<N){
                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++;
                        }
                    }

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

                //cout<<i<<"dist "<<dist<<endl;
                if(dist!=-1){
                    oc[dist%len].push_back(dist);
                }
            }
        }

        for(auto e: oc){
            sort(e.begin(), e.end());
        }

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

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

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

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

  
}

Compilation message

garden.cpp: In lambda function:
garden.cpp:74:14: warning: unused variable 'e' [-Wunused-variable]
   74 |     for(auto e:ch){
      |              ^
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
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -