oj.uz

Submission #1039487

# Submission time Handle Problem Language Result Execution time Memory
1039487 2024-07-31T00:35:26 Z vjudge1 Highway Tolls (IOI18_highway) C++17
0 / 100
 31 ms 36144 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define M 1<<17
using namespace std;
int par[M],dep[M],ord[M],pos[M],CC;
vector<pair<int,int>>adj[M];
void dfs(int n,int p){
    ord[pos[n]=++CC]=n;
    for(auto [i,k]:adj[n])
        if(i-p)
            dep[i]=dep[n]+1,
            par[i]=k,dfs(i,n);
}
void doanswer(int endpt,int N,int A,int B,long long D){
    CC=0;
    dep[endpt]=0;
    dfs(endpt,-1);
    vector<int>v;
    for(int i=0;i<N;i++)
        if(dep[i]==D)
            v.push_back(i);
    while(v.size()>1){
        vector<int>a,b;
        for(int i=0;i<v.size();i++)
            if(i%2)a.push_back(v[i]);
            else b.push_back(v[i]);
        vector<int>edg(N-1);
        for(auto i:a)
            edg[par[i]]=1;
        if(ask(edg)==A*D)
            v=b;
        else v=a;
    }
    answer(endpt,v[0]);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    for(int i=0;i<N-1;i++)
        adj[U[i]].push_back({V[i],i}),
        adj[V[i]].push_back({U[i],i});
    dfs(0,0);
    long long D=ask(vector<int>(N-1,0))/A;
    int res=1e9,l=1,r=N-1;
    while(l<=r){
        int mid=l+r>>1;
        vector<int>v(N-1);
        for(int i=1;i<=mid;i++)
            v[par[ord[i]]]=1;
        if(ask(v)>D)
            res=mid,l=mid+1;
        else r=mid-1;
    }
    doanswer(ord[res],N,A,B,D);
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5720 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 1 ms 4696 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 Runtime error 31 ms 36144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 32344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -