oj.uz

Submission #1039490

# Submission time Handle Problem Language Result Execution time Memory
1039490 2024-07-31T00:39:55 Z vjudge1 Highway Tolls (IOI18_highway) C++17
51 / 100
 96 ms 36192 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=2,r=N;
    while(l<=r){
        int mid=l+r>>1;
        vector<int>v(N-1);
        for(int i=2;i<=mid;i++)
            v[par[ord[i]]]=1;
        if(ask(v)<D*B)
            l=mid+1;
        else res=mid,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
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 8 ms 5332 KB Output is correct
3 Correct 86 ms 10544 KB Output is correct
4 Correct 79 ms 10368 KB Output is correct
5 Correct 78 ms 10500 KB Output is correct
6 Correct 83 ms 10416 KB Output is correct
7 Correct 77 ms 10512 KB Output is correct
8 Correct 73 ms 10460 KB Output is correct
9 Correct 94 ms 10540 KB Output is correct
10 Correct 85 ms 10508 KB Output is correct
11 Correct 82 ms 11188 KB Output is correct
12 Correct 78 ms 11780 KB Output is correct
13 Correct 77 ms 11316 KB Output is correct
14 Correct 92 ms 11280 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5720 KB Output is correct
2 Correct 17 ms 7060 KB Output is correct
3 Correct 25 ms 8240 KB Output is correct
4 Correct 65 ms 15464 KB Output is correct
5 Correct 56 ms 15440 KB Output is correct
6 Correct 69 ms 15460 KB Output is correct
7 Correct 66 ms 15456 KB Output is correct
8 Correct 60 ms 15456 KB Output is correct
9 Correct 64 ms 15476 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 8 ms 5208 KB Output is correct
3 Correct 59 ms 9108 KB Output is correct
4 Correct 73 ms 10368 KB Output is correct
5 Correct 89 ms 10392 KB Output is correct
6 Correct 76 ms 10384 KB Output is correct
7 Correct 74 ms 10384 KB Output is correct
8 Correct 69 ms 10372 KB Output is correct
9 Correct 87 ms 10400 KB Output is correct
10 Correct 89 ms 10228 KB Output is correct
11 Correct 96 ms 10340 KB Output is correct
12 Correct 84 ms 11784 KB Output is correct
13 Correct 85 ms 11100 KB Output is correct
14 Correct 77 ms 11504 KB Output is correct
15 Correct 76 ms 10504 KB Output is correct
16 Correct 84 ms 10392 KB Output is correct
17 Correct 95 ms 11552 KB Output is correct
18 Correct 83 ms 11468 KB Output is correct
19 Correct 73 ms 10392 KB Output is correct
20 Correct 79 ms 12292 KB Output is correct
21 Correct 73 ms 11584 KB Output is correct
22 Correct 65 ms 11708 KB Output is correct
23 Correct 62 ms 11148 KB Output is correct
24 Correct 70 ms 11632 KB Output is correct
25 Correct 90 ms 14836 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 36192 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 33 ms 32336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -