oj.uz

Submission #1039485

# Submission time Handle Problem Language Result Execution time Memory
1039485 2024-07-31T00:08:50 Z vjudge1 Highway Tolls (IOI18_highway) C++17
12 / 100
 222 ms 262144 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int par[200100],dep[200100];
vector<pair<int,int>>adj[200100];
void dfs(int n,int p){
    for(auto [i,k]:adj[n])
        if(i-p)
            dep[i]=dep[n]+1,
            par[i]=k,dfs(i,n);
}
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);
    int D=ask(vector<int>(N-1,0))/A;
    vector<int>v;
    for(int i=1;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)==(long long)A*D)
            v=b;
        else v=a;
    }
    answer(0,v[0]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, 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++)
      |                     ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 10 ms 5720 KB Output is correct
3 Correct 72 ms 10912 KB Output is correct
4 Correct 64 ms 11100 KB Output is correct
5 Correct 70 ms 11104 KB Output is correct
6 Correct 80 ms 11012 KB Output is correct
7 Correct 63 ms 10960 KB Output is correct
8 Correct 72 ms 11120 KB Output is correct
9 Correct 68 ms 10976 KB Output is correct
10 Correct 70 ms 10992 KB Output is correct
11 Correct 69 ms 11724 KB Output is correct
12 Correct 60 ms 12368 KB Output is correct
13 Correct 63 ms 11760 KB Output is correct
14 Correct 73 ms 11344 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6232 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 3 ms 4952 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 220 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 222 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -