oj.uz

답안 #933905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933905 2024-02-26T14:48:13 Z kim 통행료 (IOI18_highway) C++17
30 / 100
 201 ms 12272 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second

int n,m;
pii edge[130005];
vector<pii> graph[90005];
vector<int> tmp,ans;
ll mn_ask,dist;
bitset<90005> vis;
int tour[90005];

int solve1(int U){
    int id=0;
    queue<int> q;
    q.emplace(U);
    vis=0;
    vis[U]=1;
    tour[U]=0;
    while(q.size()){
        int u=q.front(); q.pop();
        for(auto &[v,i]:graph[u]){
            if(vis[v]) continue;
            vis[v]=1;
            q.emplace(v);
            tour[v]=++id;
        }
    }
    int l=0,r=id;
    while(l<r){
        int mid=l+r>>1;
        for(int i=0;i<m;++i){
            auto &[u,v]=edge[i];
            if(tour[u]<=mid&&tour[v]<=mid) tmp[i]=0;
            else tmp[i]=1;
        }
        if(ask(tmp)==mn_ask) r=mid;
        else l=mid+1;
    }
    for(int i=0;i<n;++i){
        if(tour[i]==l){
            ans.eb(i);
            return i;
        }
    }
}
int solve2(int U){
    int id=0;
    queue<pii> q;
    q.emplace(U,0);
    vis=0;
    vis[U]=1;
    tour[U]=0;
    while(q.size()){
        auto [u,d]=q.front(); q.pop();
        for(auto &[v,i]:graph[u]){
            if(vis[v]) continue;
            vis[v]=1;
            if(d+1<dist) q.emplace(v,d+1);
            tour[v]=++id;
        }
    }
    int l=0,r=id;
    while(l<r){
        int mid=l+r>>1;
        for(int i=0;i<m;++i){
            auto &[u,v]=edge[i];
            if(tour[u]<=mid&&tour[v]<=mid) tmp[i]=0;
            else tmp[i]=1;
        }
        if(ask(tmp)==mn_ask) r=mid;
        else l=mid+1;
    }
    for(int i=0;i<n;++i){
        if(tour[i]==l){
            ans.eb(i);
            return i;
        }
    }
}
void solve3(int U){
    queue<pii> q;
    q.emplace(U,0);
    vis=0;
    vis[U]=1;
    vector<int> tmp2(tmp.size(),1);
    vector<pii> vec;
    while(q.size()){
        auto [u,d]=q.front(); q.pop();
        for(auto &[v,id]:graph[u]){
            if(vis[v]) continue;
            if(d+1<dist) q.emplace(v,d+1), tmp2[id]=0;
            else if(d+1==dist) vec.eb(v,id);
            vis[v]=1;
        }
    }
    int l=0,r=vec.size();
    while(l<r){
        int mid=l+r>>1;
        tmp=tmp2;
        for(int i=0;i<=mid;++i) tmp[vec[i].s]=0;
        if(ask(tmp)==mn_ask) r=mid;
        else l=mid+1;
    }
    ans.eb(vec[l].f);
}

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){
        edge[i]={U[i],V[i]};
        graph[U[i]].eb(V[i],i);
        graph[V[i]].eb(U[i],i);
    }
    tmp.assign(m,0);
    mn_ask=ask(tmp), dist=mn_ask/A;
    solve3(solve2(solve1(0)));
    answer(ans[1],ans[2]);
}
/*
15 15  99 100  9 10
0 1
1 3
3 5
5 7
7 9
9 11
11 13
13 14
14 12
12 10
10 8
8 6
6 4
4 2
2 0
*/

Compilation message

highway.cpp: In function 'int solve1(int)':
highway.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'int solve2(int)':
highway.cpp:70:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'void solve3(int)':
highway.cpp:104:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'int solve1(int)':
highway.cpp:20:16: warning: control reaches end of non-void function [-Wreturn-type]
   20 |     queue<int> q;
      |                ^
highway.cpp: In function 'int solve2(int)':
highway.cpp:54:16: warning: control reaches end of non-void function [-Wreturn-type]
   54 |     queue<pii> q;
      |                ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2752 KB Output is correct
2 Correct 2 ms 2752 KB Output is correct
3 Correct 1 ms 2752 KB Output is correct
4 Correct 1 ms 2756 KB Output is correct
5 Correct 1 ms 3016 KB Output is correct
6 Correct 1 ms 2748 KB Output is correct
7 Correct 1 ms 2760 KB Output is correct
8 Correct 1 ms 2756 KB Output is correct
9 Correct 1 ms 2756 KB Output is correct
10 Correct 2 ms 2752 KB Output is correct
11 Correct 1 ms 2752 KB Output is correct
12 Correct 1 ms 2752 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2816 KB Output is correct
2 Correct 14 ms 3536 KB Output is correct
3 Correct 110 ms 9864 KB Output is correct
4 Correct 161 ms 9872 KB Output is correct
5 Correct 114 ms 9644 KB Output is correct
6 Correct 114 ms 9472 KB Output is correct
7 Correct 124 ms 9512 KB Output is correct
8 Correct 106 ms 9648 KB Output is correct
9 Correct 99 ms 9444 KB Output is correct
10 Correct 118 ms 9876 KB Output is correct
11 Correct 93 ms 8792 KB Output is correct
12 Correct 131 ms 9264 KB Output is correct
13 Correct 123 ms 9084 KB Output is correct
14 Correct 102 ms 8704 KB Output is correct

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 3464 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3076 KB Output is correct
2 Correct 10 ms 3512 KB Output is correct
3 Incorrect 61 ms 7792 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 3496 KB Output is correct
2 Correct 21 ms 3652 KB Output is correct
3 Correct 127 ms 10284 KB Output is correct
4 Correct 163 ms 11032 KB Output is correct
5 Correct 201 ms 12048 KB Output is correct
6 Correct 165 ms 12044 KB Output is correct
7 Correct 166 ms 12272 KB Output is correct
8 Correct 169 ms 11980 KB Output is correct
9 Correct 121 ms 10276 KB Output is correct
10 Correct 120 ms 10988 KB Output is correct
11 Correct 127 ms 11060 KB Output is correct
12 Correct 141 ms 11680 KB Output is correct
13 Correct 160 ms 11956 KB Output is correct
14 Correct 161 ms 12180 KB Output is correct
15 Correct 170 ms 11964 KB Output is correct
16 Correct 182 ms 11124 KB Output is correct
17 Correct 102 ms 10384 KB Output is correct
18 Correct 115 ms 10864 KB Output is correct
19 Correct 100 ms 10912 KB Output is correct
20 Correct 133 ms 11228 KB Output is correct
21 Correct 123 ms 11384 KB Output is correct

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 3496 KB Output is correct
2 Correct 16 ms 3556 KB Output is correct
3 Correct 107 ms 10020 KB Output is correct
4 Incorrect 131 ms 10740 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -