oj.uz

Submission #965526

# Submission time Handle Problem Language Result Execution time Memory
965526 2024-04-18T19:14:58 Z FEDIKUS Highway Tolls (IOI18_highway) C++17
100 / 100
 312 ms 22632 KB 
#include "highway.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn=90010;

vector<pair<int,int> > g[maxn];
int intime[maxn];
bool posetio[maxn];
vector<int> nisu;
vector<pair<int,int> > g2[maxn];
vector<int> redosled;

void bfs(int n,int m,int prva,int poc1,int poc2){
  queue<int> bfs;
  bfs.push(poc1);
  bfs.push(poc2);
  posetio[poc1]=true;
  posetio[poc2]=true;
  redosled.push_back(prva);
  g2[poc1].push_back({poc2,prva});
  g2[poc2].push_back({poc1,prva});

  int t=0;
  set<int> jesu;
  jesu.emplace(prva);

  while(!bfs.empty()){
    int node=bfs.front();
    intime[node]=t++;
    bfs.pop();

    for(auto [u,ind]:g[node]){
      if(posetio[u]) continue;
      if(ind<prva) continue;
      posetio[u]=true;
      bfs.push(u);

      g2[node].push_back({u,ind});
      g2[u].push_back({node,ind});

      redosled.push_back(ind);
      jesu.emplace(ind);
    }
  }
  for(int i=0;i<m;i++) if(jesu.find(i)==jesu.end()) nisu.push_back(i);
}

bool bio[maxn];
set<int> tren;
vector<int> red;

void dfs(int node){
  bio[node]=true;
  for(auto [u,ind]:g2[node]){
    if(bio[u]) continue;
    tren.emplace(ind);
    dfs(u);
  }
}

int uradi(int n,int m,ll bez,int prva,int poc1,int poc2,vector<int> &u,vector<int> &v){
  tren.clear();
  for(int i=0;i<n;i++) bio[i]=false;
  for(auto [u,ind]:g2[poc1]) if(u!=poc2) bio[u]=true;
  dfs(poc1);
  red.clear();
  for(int i:redosled) if(tren.find(i)!=tren.end()) red.push_back(i);

  int l=0;
  int r=int(red.size())-1; // ?
  int ret=-1;
  while(l<=r){
    int mid=l+(r-l)/2;

    vector<int> w(m,0);
    fill(w.begin(),w.begin()+prva,1);
    for(int i:nisu) w[i]=1;
    for(int i=mid;i<int(red.size());i++){
      w[red[i]]=1;
    }
    if(ask(w)>bez){
      ret=mid;
      l=mid+1;
    }else r=mid-1;
  }

  if(ret==0) return poc2;

  if(intime[u[red[ret]]]>intime[v[red[ret]]]){
    return u[red[ret]];
  }else return v[red[ret]];
}

void find_pair(int n,vector<int> u,vector<int> v,int a,int b) {
  int m=u.size();
  int prva=0;
  int l=1,r=m;
  ll bez=ask(vector<int>(m,0));
  while(l<=r){
    int mid=l+(r-l)/2;
    vector<int> w(m,0);
    fill(w.begin(),w.begin()+mid,1);
    if(ask(w)>bez){
      prva=mid;
      r=mid-1;
    }else l=mid+1;
  }

  prva--;

  for(int i=0;i<m;i++){
    g[u[i]].push_back({v[i],i});
    g[v[i]].push_back({u[i],i});
  }

  bfs(n,m,prva,u[prva],v[prva]);

  int lik1=uradi(n,m,bez,prva,u[prva],v[prva],u,v);
  int lik2=uradi(n,m,bez,prva,v[prva],u[prva],u,v);

  //cout<<lik1<<" "<<lik2<<"\n";

  answer(lik1,lik2);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5112 KB Output is correct
2 Correct 2 ms 5108 KB Output is correct
3 Correct 1 ms 5112 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 2 ms 5116 KB Output is correct
6 Correct 1 ms 5112 KB Output is correct
7 Correct 1 ms 5116 KB Output is correct
8 Correct 1 ms 5108 KB Output is correct
9 Correct 1 ms 5116 KB Output is correct
10 Correct 2 ms 5112 KB Output is correct
11 Correct 1 ms 5108 KB Output is correct
12 Correct 1 ms 5112 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5132 KB Output is correct
2 Correct 22 ms 6660 KB Output is correct
3 Correct 153 ms 17540 KB Output is correct
4 Correct 153 ms 17116 KB Output is correct
5 Correct 203 ms 18932 KB Output is correct
6 Correct 156 ms 15360 KB Output is correct
7 Correct 139 ms 14888 KB Output is correct
8 Correct 212 ms 19012 KB Output is correct
9 Correct 146 ms 15240 KB Output is correct
10 Correct 146 ms 16660 KB Output is correct
11 Correct 85 ms 11768 KB Output is correct
12 Correct 200 ms 18820 KB Output is correct
13 Correct 202 ms 19024 KB Output is correct
14 Correct 183 ms 19596 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6968 KB Output is correct
2 Correct 28 ms 8856 KB Output is correct
3 Correct 34 ms 7340 KB Output is correct
4 Correct 136 ms 18548 KB Output is correct
5 Correct 132 ms 18712 KB Output is correct
6 Correct 99 ms 21032 KB Output is correct
7 Correct 84 ms 10928 KB Output is correct
8 Correct 101 ms 19632 KB Output is correct
9 Correct 78 ms 13652 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5128 KB Output is correct
2 Correct 18 ms 6308 KB Output is correct
3 Correct 167 ms 15788 KB Output is correct
4 Correct 138 ms 16764 KB Output is correct
5 Correct 73 ms 11156 KB Output is correct
6 Correct 81 ms 10872 KB Output is correct
7 Correct 101 ms 14496 KB Output is correct
8 Correct 89 ms 11660 KB Output is correct
9 Correct 170 ms 17564 KB Output is correct
10 Correct 188 ms 15804 KB Output is correct
11 Correct 219 ms 18348 KB Output is correct
12 Correct 171 ms 18648 KB Output is correct
13 Correct 158 ms 17408 KB Output is correct
14 Correct 100 ms 12496 KB Output is correct
15 Correct 87 ms 11104 KB Output is correct
16 Correct 64 ms 10832 KB Output is correct
17 Correct 202 ms 18064 KB Output is correct
18 Correct 188 ms 19768 KB Output is correct
19 Correct 75 ms 10928 KB Output is correct
20 Correct 76 ms 10820 KB Output is correct
21 Correct 87 ms 16192 KB Output is correct
22 Correct 123 ms 13684 KB Output is correct
23 Correct 147 ms 19468 KB Output is correct
24 Correct 131 ms 19676 KB Output is correct
25 Correct 209 ms 22632 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6780 KB Output is correct
2 Correct 18 ms 6600 KB Output is correct
3 Correct 207 ms 19188 KB Output is correct
4 Correct 203 ms 18212 KB Output is correct
5 Correct 194 ms 19564 KB Output is correct
6 Correct 254 ms 20680 KB Output is correct
7 Correct 228 ms 20140 KB Output is correct
8 Correct 223 ms 19640 KB Output is correct
9 Correct 102 ms 11048 KB Output is correct
10 Correct 112 ms 14216 KB Output is correct
11 Correct 130 ms 15016 KB Output is correct
12 Correct 225 ms 19112 KB Output is correct
13 Correct 221 ms 19704 KB Output is correct
14 Correct 247 ms 20596 KB Output is correct
15 Correct 248 ms 20316 KB Output is correct
16 Correct 156 ms 15300 KB Output is correct
17 Correct 147 ms 16944 KB Output is correct
18 Correct 80 ms 12416 KB Output is correct
19 Correct 151 ms 18440 KB Output is correct
20 Correct 123 ms 14692 KB Output is correct
21 Correct 249 ms 21544 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6692 KB Output is correct
2 Correct 17 ms 6700 KB Output is correct
3 Correct 243 ms 19564 KB Output is correct
4 Correct 222 ms 19016 KB Output is correct
5 Correct 230 ms 19364 KB Output is correct
6 Correct 256 ms 20320 KB Output is correct
7 Correct 173 ms 19016 KB Output is correct
8 Correct 253 ms 19444 KB Output is correct
9 Correct 205 ms 19456 KB Output is correct
10 Correct 217 ms 20116 KB Output is correct
11 Correct 235 ms 20640 KB Output is correct
12 Correct 216 ms 20192 KB Output is correct
13 Correct 95 ms 11780 KB Output is correct
14 Correct 124 ms 11928 KB Output is correct
15 Correct 172 ms 16468 KB Output is correct
16 Correct 155 ms 13708 KB Output is correct
17 Correct 119 ms 15216 KB Output is correct
18 Correct 142 ms 13676 KB Output is correct
19 Correct 257 ms 18860 KB Output is correct
20 Correct 243 ms 20020 KB Output is correct
21 Correct 286 ms 20240 KB Output is correct
22 Correct 240 ms 20328 KB Output is correct
23 Correct 270 ms 20692 KB Output is correct
24 Correct 267 ms 20748 KB Output is correct
25 Correct 272 ms 19932 KB Output is correct
26 Correct 248 ms 20152 KB Output is correct
27 Correct 139 ms 15132 KB Output is correct
28 Correct 132 ms 18624 KB Output is correct
29 Correct 171 ms 19788 KB Output is correct
30 Correct 147 ms 19124 KB Output is correct
31 Correct 137 ms 17888 KB Output is correct
32 Correct 129 ms 18436 KB Output is correct
33 Correct 151 ms 20360 KB Output is correct
34 Correct 158 ms 17080 KB Output is correct
35 Correct 112 ms 17876 KB Output is correct
36 Correct 161 ms 19096 KB Output is correct
37 Correct 169 ms 17896 KB Output is correct
38 Correct 130 ms 18716 KB Output is correct
39 Correct 243 ms 21404 KB Output is correct
40 Correct 312 ms 21532 KB Output is correct
41 Correct 245 ms 21316 KB Output is correct
42 Correct 247 ms 20712 KB Output is correct