oj.uz

Submission #933856

# Submission time Handle Problem Language Result Execution time Memory
933856 2024-02-26T12:23:24 Z kim Highway Tolls (IOI18_highway) C++17
51 / 100
 151 ms 12800 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

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

void solve2(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);
}

int pre[90005];
void play(int n,vector<int> &U,vector<int> &V,int u0){
	vis=0;
	int m=U.size();
	int id=0;
	{
		queue<int> q;
		q.emplace(u0);
		vis[u0]=1;
		while(q.size()){
			int u=q.front(); q.pop();
			pre[u]=++id;
			for(auto &[v,id]:graph[u]){
				if(vis[v]) continue;
				vis[v]=1;
				q.emplace(v);
			}
		}
	}
	int l=1,r=id;
	while(l<r){
		int mid=l+r>>1;
		for(int i=0;i<m;++i){
			if(pre[U[i]]<=mid&&pre[V[i]]<=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(pre[i]==l){
			ans.eb(i);
            break;
		}
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    for(int i=0;i<U.size();++i){
        edge[i]={U[i],V[i]};
        graph[U[i]].eb(V[i],i);
        graph[V[i]].eb(U[i],i);
    }
    tmp.assign(U.size(),0);
    mn_ask=ask(tmp), dist=mn_ask/A;
    play(N,U,V,0);
    solve2(ans[0]);
    answer(ans[0],ans[1]);
}

Compilation message

highway.cpp: In function 'void solve2(int)':
highway.cpp:34:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'void play(int, std::vector<int>&, std::vector<int>&, int)':
highway.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int mid=l+r>>1;
      |           ~^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<U.size();++i){
      |                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2756 KB Output is correct
2 Correct 1 ms 2756 KB Output is correct
3 Correct 1 ms 2760 KB Output is correct
4 Correct 1 ms 2752 KB Output is correct
5 Correct 1 ms 2756 KB Output is correct
6 Correct 1 ms 2760 KB Output is correct
7 Correct 1 ms 2752 KB Output is correct
8 Correct 1 ms 2752 KB Output is correct
9 Correct 1 ms 2756 KB Output is correct
10 Correct 1 ms 2756 KB Output is correct
11 Correct 1 ms 2756 KB Output is correct
12 Correct 1 ms 2988 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2820 KB Output is correct
2 Correct 8 ms 3456 KB Output is correct
3 Correct 96 ms 10052 KB Output is correct
4 Correct 95 ms 9556 KB Output is correct
5 Correct 93 ms 10012 KB Output is correct
6 Correct 89 ms 9236 KB Output is correct
7 Correct 90 ms 9680 KB Output is correct
8 Correct 88 ms 9632 KB Output is correct
9 Correct 77 ms 9660 KB Output is correct
10 Correct 95 ms 9788 KB Output is correct
11 Correct 80 ms 8840 KB Output is correct
12 Correct 95 ms 8940 KB Output is correct
13 Correct 78 ms 8932 KB Output is correct
14 Correct 67 ms 8696 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3460 KB Output is correct
2 Correct 14 ms 4084 KB Output is correct
3 Correct 21 ms 4724 KB Output is correct
4 Correct 58 ms 8556 KB Output is correct
5 Correct 59 ms 8552 KB Output is correct
6 Correct 65 ms 8556 KB Output is correct
7 Correct 57 ms 8552 KB Output is correct
8 Correct 59 ms 8720 KB Output is correct
9 Correct 69 ms 9060 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Correct 10 ms 3448 KB Output is correct
3 Correct 56 ms 8036 KB Output is correct
4 Correct 80 ms 9144 KB Output is correct
5 Correct 78 ms 9396 KB Output is correct
6 Correct 80 ms 9632 KB Output is correct
7 Correct 75 ms 9872 KB Output is correct
8 Correct 90 ms 9612 KB Output is correct
9 Correct 93 ms 9836 KB Output is correct
10 Correct 101 ms 10356 KB Output is correct
11 Correct 88 ms 8788 KB Output is correct
12 Correct 84 ms 8800 KB Output is correct
13 Correct 78 ms 8560 KB Output is correct
14 Correct 89 ms 9032 KB Output is correct
15 Correct 76 ms 9384 KB Output is correct
16 Correct 74 ms 9384 KB Output is correct
17 Correct 87 ms 8924 KB Output is correct
18 Correct 86 ms 8932 KB Output is correct
19 Correct 76 ms 9628 KB Output is correct
20 Correct 76 ms 8556 KB Output is correct
21 Correct 78 ms 10584 KB Output is correct
22 Correct 78 ms 10564 KB Output is correct
23 Correct 85 ms 10468 KB Output is correct
24 Correct 77 ms 10352 KB Output is correct
25 Correct 75 ms 9004 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3496 KB Output is correct
2 Correct 12 ms 3656 KB Output is correct
3 Correct 108 ms 10592 KB Output is correct
4 Correct 106 ms 10784 KB Output is correct
5 Correct 151 ms 12680 KB Output is correct
6 Correct 128 ms 12292 KB Output is correct
7 Correct 133 ms 12800 KB Output is correct
8 Incorrect 137 ms 12084 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 11 ms 3496 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -