oj.uz

Submission #1039632

# Submission time Handle Problem Language Result Execution time Memory
1039632 2024-07-31T06:17:31 Z vjudge1 Highway Tolls (IOI18_highway) C++17
5 / 100
 112 ms 18876 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define K 1<<17
using namespace std;
int par[K],dep[K],ord[K],pos[K],CC,bfspar[2][K],bfspari[2][K],bfsdis[2][K];
vector<pair<int,int>>adj[K];
void bfs(int n,int i){
    queue<int>q;
    memset(bfsdis[i],-1,sizeof par);
    q.push(n);
    bfsdis[i][n]=0;
    bfspar[i][n]=-1;
    while(q.size()){
        int x=q.front(),d=bfsdis[i][x]; q.pop();
        for(auto [j,k]:adj[x]) if(bfsdis[i][j]<0)
            bfspar[i][j]=x,bfspari[i][j]=k,
            bfsdis[i][j]=d+1,q.push(j);
    }
}
void dfs(int n,int in){
    pos[n]=++CC;
    for(auto [i,k]:adj[n])
        if(bfspar[in][i]==n)
            dep[i]=dep[n]+1,
            par[i]=k,dfs(i,in);
}
int whicho(int pivot,int N,int ind,int M,vector<int>v,int D){
    dfs(pivot,ind);
    sort(v.begin(),v.end(),[](int a,int b){
        return pos[a]<pos[b];
    });
    int l=1,r=v.size()-1,res=1;
    while(l<=r){
        int mid=l+r>>1;
        vector<int>V(M,1);
        for(int i=mid;i<v.size();i++)
            V[bfspari[ind][v[i]]]=0;
        if(ask(V)<D)
            l=res=mid+1;
        else r=mid-1;
    }
    return v[res-1];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M=U.size();
    for(int i=0;i<M;i++)
        adj[U[i]].push_back({V[i],i}),
        adj[V[i]].push_back({U[i],i});
    long long D=ask(vector<int>(M,0))/A;
    int res=1e9,l=1,r=M;
    while(l<=r){
        int mid=l+r>>1;
        vector<int>v(M);
        for(int i=0;i<mid;i++)
            v[i]=1;
        if(ask(v)>D*A)
            res=r=mid-1;
        else l=mid+1;
    }
    int a=U[res],b=V[res];
    bfs(a,0);
    bfs(b,1);
    vector<int>sta,stb;
    for(int i=0;i<N;i++)
        if(bfsdis[0][i]<bfsdis[1][i])
            sta.push_back(i);
        else if(bfsdis[0][i]-bfsdis[1][i])
            stb.push_back(i);
    answer(whicho(a,N,0,M,sta,D*B),whicho(b,N,1,M,stb,D*B));
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 11 ms 5464 KB Output is correct
3 Correct 107 ms 12908 KB Output is correct
4 Correct 112 ms 12896 KB Output is correct
5 Correct 112 ms 12916 KB Output is correct
6 Correct 95 ms 12908 KB Output is correct
7 Correct 111 ms 12908 KB Output is correct
8 Correct 98 ms 12892 KB Output is correct
9 Correct 98 ms 12912 KB Output is correct
10 Correct 110 ms 12912 KB Output is correct
11 Correct 109 ms 14012 KB Output is correct
12 Correct 110 ms 14600 KB Output is correct
13 Correct 103 ms 14172 KB Output is correct
14 Incorrect 97 ms 14160 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5976 KB Output is correct
2 Correct 18 ms 7512 KB Output is correct
3 Correct 26 ms 9248 KB Output is correct
4 Correct 77 ms 16712 KB Output is correct
5 Correct 87 ms 16892 KB Output is correct
6 Correct 86 ms 18336 KB Output is correct
7 Correct 73 ms 18876 KB Output is correct
8 Correct 76 ms 17676 KB Output is correct
9 Incorrect 88 ms 17580 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 13 ms 5384 KB Output is correct
3 Correct 68 ms 11068 KB Output is correct
4 Correct 91 ms 12912 KB Output is correct
5 Correct 90 ms 12916 KB Output is correct
6 Correct 85 ms 12912 KB Output is correct
7 Correct 91 ms 12908 KB Output is correct
8 Correct 84 ms 12884 KB Output is correct
9 Incorrect 89 ms 12908 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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