oj.uz

Submission #888438

# Submission time Handle Problem Language Result Execution time Memory
888438 2023-12-17T12:02:17 Z kim Highway Tolls (IOI18_highway) C++17
51 / 100
 154 ms 18596 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
#define eb emplace_back

int N,M;
vector<pii> adj[90005],adj2[90005];
vector<int> temp,ans;
pii edge[130005];
bool flag[90005];
int tour[90005],node[90005],id0;
ll mn;

void bfs(int u){
  queue<int> q;
  q.push(u);
  flag[u]=1;
  while(q.size()){
    int u=q.front(); q.pop();
    for(auto &[v,i]:adj[u]){
      if(!flag[v]){
        q.push(v);
        flag[v]=1;
        adj2[u].eb(v,i),adj2[v].eb(u,i);
      }
    }
  }
}
void dfs(int u,int p){
  tour[u]=++id0;
  node[id0]=u;
  for(auto &[v,i]:adj2[u]){
    if(v!=p) dfs(v,u);
  }
}

int play(int U){
  for(int i=0;i<N;++i) adj2[i].clear(),flag[i]=0;
  bfs(U);
  id0=0,dfs(U,U);
  int l=1,r=id0;
  while(l<r){
    int mid=l+((r-l)>>1);

    for(int i=0;i<M;++i){
      auto &[u,v]=edge[i];
      if(tour[u]<=mid&&tour[v]<=mid) temp[i]=0;
      else temp[i]=1;
    }

    if(ask(temp)==mn) r=mid;
    else l=mid+1;
  }
  ans.eb(node[l]);
  return node[l];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  ::N=N,M=U.size();
  for(int i=0;i<M;++i){
    adj[U[i]].eb(V[i],i);
    adj[V[i]].eb(U[i],i);
    edge[i]={U[i],V[i]};
    temp.eb(0);
  }
  mn=ask(temp);
  play(play(0));
  answer(ans[0],ans[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6308 KB Output is correct
2 Correct 2 ms 6312 KB Output is correct
3 Correct 2 ms 6308 KB Output is correct
4 Correct 2 ms 6468 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6560 KB Output is correct
7 Correct 2 ms 6304 KB Output is correct
8 Correct 2 ms 6312 KB Output is correct
9 Correct 2 ms 6312 KB Output is correct
10 Correct 2 ms 6312 KB Output is correct
11 Correct 2 ms 6232 KB Output is correct
12 Correct 2 ms 6308 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6364 KB Output is correct
2 Correct 14 ms 7252 KB Output is correct
3 Correct 135 ms 15016 KB Output is correct
4 Correct 122 ms 15708 KB Output is correct
5 Correct 154 ms 15204 KB Output is correct
6 Correct 134 ms 15712 KB Output is correct
7 Correct 138 ms 15720 KB Output is correct
8 Correct 122 ms 15216 KB Output is correct
9 Correct 118 ms 15500 KB Output is correct
10 Correct 129 ms 15680 KB Output is correct
11 Correct 124 ms 15828 KB Output is correct
12 Correct 150 ms 15576 KB Output is correct
13 Correct 124 ms 15448 KB Output is correct
14 Correct 107 ms 15328 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7696 KB Output is correct
2 Correct 18 ms 8980 KB Output is correct
3 Correct 25 ms 10304 KB Output is correct
4 Correct 71 ms 18096 KB Output is correct
5 Correct 113 ms 18092 KB Output is correct
6 Correct 110 ms 18596 KB Output is correct
7 Correct 95 ms 18332 KB Output is correct
8 Correct 75 ms 18092 KB Output is correct
9 Correct 80 ms 18336 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6368 KB Output is correct
2 Correct 10 ms 7300 KB Output is correct
3 Correct 80 ms 13360 KB Output is correct
4 Correct 115 ms 15712 KB Output is correct
5 Correct 101 ms 15724 KB Output is correct
6 Correct 107 ms 15452 KB Output is correct
7 Correct 111 ms 15684 KB Output is correct
8 Correct 103 ms 15488 KB Output is correct
9 Correct 121 ms 15480 KB Output is correct
10 Correct 114 ms 15740 KB Output is correct
11 Correct 109 ms 14856 KB Output is correct
12 Correct 127 ms 15872 KB Output is correct
13 Correct 118 ms 15484 KB Output is correct
14 Correct 119 ms 16536 KB Output is correct
15 Correct 98 ms 15268 KB Output is correct
16 Correct 95 ms 15212 KB Output is correct
17 Correct 108 ms 15396 KB Output is correct
18 Correct 100 ms 15800 KB Output is correct
19 Correct 100 ms 15256 KB Output is correct
20 Correct 106 ms 16436 KB Output is correct
21 Correct 92 ms 15924 KB Output is correct
22 Correct 79 ms 15664 KB Output is correct
23 Correct 91 ms 16016 KB Output is correct
24 Correct 102 ms 16268 KB Output is correct
25 Correct 100 ms 17856 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 7436 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7440 KB Output is correct
2 Incorrect 13 ms 7356 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -