oj.uz

Submission #888443

# Submission time Handle Problem Language Result Execution time Memory
888443 2023-12-17T12:13:36 Z kim Highway Tolls (IOI18_highway) C++17
51 / 100
 167 ms 17816 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();
    tour[u]=++id0;
    node[id0]=u;
    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;
  id0=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 6312 KB Output is correct
4 Correct 2 ms 6308 KB Output is correct
5 Correct 2 ms 6560 KB Output is correct
6 Correct 2 ms 6304 KB Output is correct
7 Correct 2 ms 6308 KB Output is correct
8 Correct 2 ms 6304 KB Output is correct
9 Correct 2 ms 6308 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 6368 KB Output is correct
2 Correct 11 ms 7248 KB Output is correct
3 Correct 125 ms 15500 KB Output is correct
4 Correct 112 ms 15452 KB Output is correct
5 Correct 122 ms 15724 KB Output is correct
6 Correct 105 ms 15212 KB Output is correct
7 Correct 113 ms 15684 KB Output is correct
8 Correct 120 ms 15640 KB Output is correct
9 Correct 108 ms 15492 KB Output is correct
10 Correct 104 ms 15456 KB Output is correct
11 Correct 106 ms 14096 KB Output is correct
12 Correct 118 ms 14588 KB Output is correct
13 Correct 115 ms 14112 KB Output is correct
14 Correct 106 ms 14356 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7076 KB Output is correct
2 Correct 19 ms 8040 KB Output is correct
3 Correct 27 ms 9128 KB Output is correct
4 Correct 75 ms 13868 KB Output is correct
5 Correct 72 ms 14112 KB Output is correct
6 Correct 67 ms 14132 KB Output is correct
7 Correct 67 ms 14112 KB Output is correct
8 Correct 74 ms 13860 KB Output is correct
9 Correct 70 ms 13884 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6360 KB Output is correct
2 Correct 12 ms 7304 KB Output is correct
3 Correct 77 ms 13372 KB Output is correct
4 Correct 103 ms 15444 KB Output is correct
5 Correct 107 ms 15476 KB Output is correct
6 Correct 95 ms 15208 KB Output is correct
7 Correct 98 ms 15248 KB Output is correct
8 Correct 124 ms 15728 KB Output is correct
9 Correct 120 ms 15948 KB Output is correct
10 Correct 125 ms 15484 KB Output is correct
11 Correct 114 ms 14812 KB Output is correct
12 Correct 105 ms 14352 KB Output is correct
13 Correct 110 ms 14356 KB Output is correct
14 Correct 111 ms 14124 KB Output is correct
15 Correct 106 ms 15500 KB Output is correct
16 Correct 92 ms 15208 KB Output is correct
17 Correct 116 ms 14336 KB Output is correct
18 Correct 121 ms 14828 KB Output is correct
19 Correct 117 ms 15500 KB Output is correct
20 Correct 107 ms 14332 KB Output is correct
21 Correct 89 ms 16156 KB Output is correct
22 Correct 89 ms 15912 KB Output is correct
23 Correct 98 ms 15712 KB Output is correct
24 Correct 97 ms 15576 KB Output is correct
25 Correct 113 ms 14548 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7436 KB Output is correct
2 Correct 13 ms 7356 KB Output is correct
3 Correct 140 ms 16172 KB Output is correct
4 Correct 129 ms 16188 KB Output is correct
5 Correct 167 ms 17816 KB Output is correct
6 Correct 155 ms 17348 KB Output is correct
7 Correct 163 ms 17800 KB Output is correct
8 Incorrect 164 ms 17192 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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