oj.uz

답안 #746148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
746148 2023-05-21T13:44:15 Z almothana05 통행료 (IOI18_highway) C++14
11 / 100
 1500 ms 18496 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int , int> >kinder[300000] , ka;
vector<int>cent , ed;
int sub[300000], vis[300000];
long long a , b , menge , cmp , comp ,numm  , kind , vase;
int st , en , mid , mit;
int centroid(int x , int f , int n){
  for(int i = 0 ; i < kinder[x].size() ; i++){
    kind = kinder[x][i].first;
    if(vis[kind] != 2 &&kind != f && sub[kind] * 2 > n){
      return centroid(kind , x , n);
    }
  }
  for(int i = 0 ; i < kinder[x].size() ; i++){
    ed[kinder[x][i].second] = 1;
  }
  vis[x] = 2;
  return x;
}
int dfs(int x){
  vis[x] = 1;
  sub[x] = 1;
  for(int i = 0 ; i < kinder[x].size() ; i++){
    kind = kinder[x][i].first;
    if(vis[kind] == 0){
      sub[x] += dfs(kind);
    }
  }
  return sub[x];
}
int bis(int x , int y , long long z ,int f , int root){
    for(int i = 0 ; i <= y ; i++){
      ed[kinder[root][i].second] = 1;
    }
    st = x ; en = y; mid = y;
    while(st <= en){
      mit = (st + en)/2;
      
        while(mid > mit){
          if(kinder[root][mid].first == f || vis[kinder[root][mid].first] == 2){
            mid--;
            continue;
          }
          ed[kinder[root][mid].second] = 0;
          mid--;
        }
        
        while(mid <= mit){
          if(kinder[root][mid].first == f || vis[kinder[root][mid].first] == 2){
            mid++;
            continue;
          }
          ed[kinder[root][mid].second] = 1;
          mid++;
        }
        if(mid > mit){
          mid--;
        }
        
      numm = ask(ed);
      if(numm >= z){
        en = mit - 1;
      }
      else{
        st = mit + 1;
      }
    }
    for(int i = 0 ; i <= y ; i++){
      ed[kinder[root][i].second] = 1;
    }
    return st;
}
long long suche(int x){
  // cout << x << "\n";
  dfs(x);
  long long nummer = centroid(x ,x , sub[x]);
  for(int i = 0 ; i < menge ; i++){
    if(vis[i] == 1){
      vis[i] = 0;
    }
  }
  // cout << nummer << ' ' << x << "\n";
  // cout << kinder[nummer].size() << "\n";
  int fater = -1,pl;
  for(int i = 0 ; i < kinder[nummer].size() ; i++ ){
    if(sub[kinder[nummer][i].first] > sub[nummer] && vis[kinder[nummer][i].first] != 2){
      fater = kinder[nummer][i].first;
      break;
    }
  }
  // cout << fater << "\n";
  cmp = ask(ed);
  // cout << cmp - comp << "\n";  
  if(nummer == x){   
    // while(true);
    if(cmp == comp){
      return nummer;
    }
    else{
      comp = cmp;
      pl = bis(0 , kinder[nummer].size() - 1 , cmp , fater , nummer );
    }
  }
  else{
    if(cmp == comp){
    // while(true); 
      return suche(x);
    }
    else if(cmp == comp + b - a){
      comp = cmp;
      // while(true);
      return nummer;
    }
    else{
      // while(true);
      comp = cmp;
      pl = bis(0 , kinder[nummer].size() - 1 , cmp , fater , nummer );
      // cout << kinder[nummer].size() << "\n";
    }
  }
  return suche(kinder[nummer][pl].first);
}





void finde(){
  cent.clear();
  ka.clear();
  for(int i = 0 ; i < menge ; i++){
    if(vis[i] == 0){
      ka.push_back({i , dfs(i)});
    }
  }
  
  for(int i = 0 ; i < ka.size() ; i++){
    cent.push_back(centroid(ka[i].first , ka[i].first , ka[i].second));
    // cout << cent[i] << ' ';
  }
  // cout << "\n";
  for(int i = 0 ; i < menge ; i++){
    if(vis[i] == 1){
      vis[i] = 0;
    }
  }
  ka.clear();
  comp = ask(ed);
  vase = comp;
  if(comp > cmp){
    st = 0 ; en = cent.size() - 2; mid = cent.size() - 1;
    while(st <= en){
      mit = (st + en)/2;
      
        while(mid > mit){
          for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
            ed[kinder[cent[mid]][i].second] = 0;
          }
          mid--;
        }
        

        while(mid <= mit){
          for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
            ed[kinder[cent[mid]][i].second] = 1;
          }
          mid++;
        }
        if(mid > mit){
          mid--;
        }
        
      numm = ask(ed);
      if(numm == comp){
        en = mit - 1;
      }
      else{
        st = mit + 1;
      }
    }
    int root , er  ,zw;
    root = cent[st];
    // cout << root << "\n";
    cent.clear();
    er = bis(0 , kinder[root].size() - 1 , cmp +b -a , -1 , root);
    // cout << er << "\n";
    if(comp == cmp + b - a){

      zw = root;
    }
    else{
      // while(true);
      zw = bis(er , kinder[root].size() - 1 , comp , -1 , root);
      // cout << zw << ' ' << kinder[root][zw].first << "\n";
      // cout << kinder[root][er].first << "\n";
      zw = suche(kinder[root][zw].first);
      // cout << zw << "\n";
    }
      er = suche(kinder[root][er].first);
    // comp = ask(ed);
    // cout << er << "\n";
    answer(er , zw);
    return;
  }
  cent.clear();
  finde();
}
void find_pair(int N, vector<int> u, vector<int> v, int A, int B) {
  a = A;
  b = B;
  menge = N;

  for(int i = 0 ; i < u.size() ; i++){
    kinder[u[i]].push_back({v[i] , i});
    kinder[v[i]].push_back({u[i] , i});
    ed.push_back(0);
  }
  cmp = ask(ed);
  finde();
}

Compilation message

highway.cpp: In function 'int centroid(int, int, int)':
highway.cpp:10:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |   for(int i = 0 ; i < kinder[x].size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
highway.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(int i = 0 ; i < kinder[x].size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'int dfs(int)':
highway.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int i = 0 ; i < kinder[x].size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'long long int suche(int)':
highway.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int i = 0 ; i < kinder[nummer].size() ; i++ ){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void finde()':
highway.cpp:139:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   for(int i = 0 ; i < ka.size() ; i++){
      |                   ~~^~~~~~~~~~~
highway.cpp:158:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |           for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
      |                           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:166:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |           for(int i = 0 ; i < kinder[cent[mid]].size() ; i++){
      |                           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:215:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |   for(int i = 0 ; i < u.size() ; i++){
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7248 KB Output is correct
2 Correct 4 ms 7360 KB Output is correct
3 Correct 4 ms 7360 KB Output is correct
4 Correct 4 ms 7248 KB Output is correct
5 Correct 4 ms 7248 KB Output is correct
6 Correct 4 ms 7248 KB Output is correct
7 Correct 4 ms 7248 KB Output is correct
8 Correct 4 ms 7364 KB Output is correct
9 Correct 5 ms 7240 KB Output is correct
10 Correct 4 ms 7248 KB Output is correct
11 Correct 6 ms 7248 KB Output is correct
12 Correct 4 ms 7248 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7376 KB Output is correct
2 Correct 16 ms 7888 KB Output is correct
3 Correct 140 ms 13192 KB Output is correct
4 Correct 102 ms 13188 KB Output is correct
5 Correct 136 ms 13188 KB Output is correct
6 Incorrect 138 ms 13188 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8528 KB Output is correct
2 Correct 27 ms 9652 KB Output is correct
3 Correct 34 ms 11004 KB Output is correct
4 Correct 90 ms 18496 KB Output is correct
5 Correct 101 ms 18396 KB Output is correct
6 Correct 95 ms 18276 KB Output is correct
7 Correct 98 ms 18276 KB Output is correct
8 Correct 117 ms 18268 KB Output is correct
9 Correct 102 ms 18268 KB Output is correct

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7408 KB Output is correct
2 Correct 11 ms 7932 KB Output is correct
3 Correct 90 ms 11916 KB Output is correct
4 Correct 132 ms 13184 KB Output is correct
5 Correct 144 ms 13216 KB Output is correct
6 Correct 117 ms 13240 KB Output is correct
7 Correct 182 ms 13416 KB Output is correct
8 Correct 146 ms 13400 KB Output is correct
9 Incorrect 117 ms 13188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3027 ms 8144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3042 ms 8056 KB Time limit exceeded
2 Halted 0 ms 0 KB -