oj.uz

Submission #888436

# Submission time Handle Problem Language Result Execution time Memory
888436 2023-12-17T11:53:53 Z kim Highway Tolls (IOI18_highway) C++17
51 / 100
 153 ms 18368 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 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){
  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) {
  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);
  bfs(0);
  play(play(0));
  answer(ans[0],ans[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6316 KB Output is correct
2 Correct 2 ms 6308 KB Output is correct
3 Correct 2 ms 6308 KB Output is correct
4 Correct 2 ms 6308 KB Output is correct
5 Correct 2 ms 6308 KB Output is correct
6 Correct 2 ms 6308 KB Output is correct
7 Correct 2 ms 6304 KB Output is correct
8 Correct 2 ms 6316 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 6304 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6360 KB Output is correct
2 Correct 12 ms 7136 KB Output is correct
3 Correct 134 ms 15204 KB Output is correct
4 Correct 110 ms 15208 KB Output is correct
5 Correct 104 ms 14972 KB Output is correct
6 Correct 115 ms 15892 KB Output is correct
7 Correct 111 ms 14972 KB Output is correct
8 Correct 95 ms 14976 KB Output is correct
9 Correct 100 ms 15436 KB Output is correct
10 Correct 147 ms 15236 KB Output is correct
11 Correct 120 ms 15372 KB Output is correct
12 Correct 102 ms 15720 KB Output is correct
13 Correct 140 ms 15756 KB Output is correct
14 Correct 106 ms 15552 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7696 KB Output is correct
2 Correct 17 ms 9224 KB Output is correct
3 Correct 41 ms 10288 KB Output is correct
4 Correct 108 ms 18340 KB Output is correct
5 Correct 129 ms 18324 KB Output is correct
6 Correct 72 ms 18108 KB Output is correct
7 Correct 97 ms 18092 KB Output is correct
8 Correct 93 ms 18340 KB Output is correct
9 Correct 81 ms 18368 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6616 KB Output is correct
2 Correct 18 ms 7248 KB Output is correct
3 Correct 73 ms 13104 KB Output is correct
4 Correct 143 ms 14972 KB Output is correct
5 Correct 109 ms 15208 KB Output is correct
6 Correct 151 ms 15208 KB Output is correct
7 Correct 133 ms 15244 KB Output is correct
8 Correct 122 ms 15228 KB Output is correct
9 Correct 132 ms 15200 KB Output is correct
10 Correct 110 ms 15704 KB Output is correct
11 Correct 107 ms 15092 KB Output is correct
12 Correct 113 ms 16580 KB Output is correct
13 Correct 116 ms 15780 KB Output is correct
14 Correct 153 ms 16088 KB Output is correct
15 Correct 97 ms 15224 KB Output is correct
16 Correct 86 ms 15212 KB Output is correct
17 Correct 144 ms 15384 KB Output is correct
18 Correct 98 ms 15372 KB Output is correct
19 Correct 104 ms 15676 KB Output is correct
20 Correct 100 ms 16408 KB Output is correct
21 Correct 85 ms 15868 KB Output is correct
22 Correct 80 ms 15652 KB Output is correct
23 Correct 120 ms 16220 KB Output is correct
24 Correct 96 ms 16272 KB Output is correct
25 Correct 120 ms 17840 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 7280 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 Incorrect 15 ms 7284 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -