oj.uz

Submission #139404

# Submission time Handle Problem Language Result Execution time Memory
139404 2019-07-31T16:10:20 Z degelo Highway Tolls (IOI18_highway) C++17
12 / 100
 430 ms 19584 KB 
#include<bits/stdc++.h>
#include "highway.h"
using namespace std;

vector<int> cam;
int A,B;

vector<int> grafo[90004];
vector<int> ek,vk,teste;
map< pair<int,int> ,int > edge;
void dfs(int v,int p,int dist,int k){
    for(int i=0;i<grafo[v].size();i++){
        int viz=grafo[v][i];
        if(viz!=p){
            if(dist==k-1){
                ek.push_back(edge[make_pair(v,viz)]);
                vk.push_back(viz);
            }
            else{
                dfs(viz,v,dist+1,k);
            }
        }
    }
}
void paint(int ini,int fim){
    for(int i=0;i<teste.size();i++){
        teste[i]=0;
    }
    for(int i=ini;i<=fim;i++){
        teste[ek[i]]=1;
    }
}
/*void answer(int s,int t){
    cout<<s<<" "<<t<<endl;
}
long long int ask(vector<int> a){
    long long int resp=0;
    for(int i=0;i<cam.size();i++){
        if(a[cam[i]]==0) resp+=A;
        else resp+=B;
    }
    return resp;
}*/
void find_pair(int n,vector<int> u,vector<int> v,int a,int b){
    for(int i=0;i<u.size();i++){
        edge[make_pair(u[i],v[i])]=i;
        edge[make_pair(v[i],u[i])]=i;
        grafo[u[i]].push_back(v[i]);
        grafo[v[i]].push_back(u[i]);
        teste.push_back(0);
    }
    long long int t1=ask(teste);
    int k=t1/a;
    dfs(0,-1,0,k);
    /*for(int i=0;i<ek.size();i++){
        cout<<ek[i]<<" "<<vk[i]<<endl;

    }*/

    int ini=0,fim=ek.size()-1;
    while(ini!=fim){
        int meio=(fim+ini)/2;
        paint(ini,meio);
        long long int t=ask(teste);
        if(t==t1){
            ini=meio+1;
        }
        else{
            fim=meio;
        }
    }
    answer(0,vk[ini]);
}
/*int main(){
    int n,m;
    cin>>n>>m;
    vector<int> u,v;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        u.push_back(a);
        v.push_back(b);
    }
    int c;
    cin>>c;
    for(int i=0;i<c;i++){
        int a;
        cin>>a;
        cam.push_back(a);
    }
    cin>>A>>B;
    find_pair(n,u,v,A,B);
}*/

Compilation message

highway.cpp: In function 'void dfs(int, int, int, int)':
highway.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<grafo[v].size();i++){
                 ~^~~~~~~~~~~~~~~~
highway.cpp: In function 'void paint(int, int)':
highway.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<teste.size();i++){
                 ~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<u.size();i++){
                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2604 KB Output is correct
2 Correct 45 ms 4204 KB Output is correct
3 Correct 430 ms 18568 KB Output is correct
4 Correct 360 ms 18588 KB Output is correct
5 Correct 354 ms 18580 KB Output is correct
6 Correct 388 ms 18448 KB Output is correct
7 Correct 352 ms 18484 KB Output is correct
8 Correct 411 ms 18588 KB Output is correct
9 Correct 315 ms 18492 KB Output is correct
10 Correct 400 ms 18528 KB Output is correct
11 Correct 322 ms 18892 KB Output is correct
12 Correct 350 ms 19392 KB Output is correct
13 Correct 316 ms 19204 KB Output is correct
14 Correct 384 ms 19584 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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