oj.uz

Submission #292873

# Submission time Handle Problem Language Result Execution time Memory
292873 2020-09-07T14:29:35 Z Atill83 Highway Tolls (IOI18_highway) C++14
12 / 100
 309 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
vector<int> sor;
vector<int> cnd;
const int MAXN = (int) 9e4 + 5;
vector<pii> adj[MAXN];
int open[MAXN];
int dep[MAXN];
long long der;
void dfs(int v, int par){
    if(dep[v] == der) {cnd.push_back(v); return;}
    for(pii u: adj[v]){
        int j = u.ff;
        if(j != par){
            dep[j] = dep[v] + 1;
            dfs(j, v);
        }
    }
}

bool dfs1(int v, int par){
    if(open[v]) return 1;
    bool vardi = 0;
    for(pii u: adj[v]){
        if(u.ff == par) continue;
        bool var = dfs1(u.ff, v);
        vardi |= var;
        if(var){
            sor[u.ss] = 0;
        }
    }
    return vardi;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    int s = 0, t;
    for(int i = 0; i < M; i++) {
        sor.push_back(0);
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    der = ask(sor) / A;

    dfs(0, -1);

    int l = 0, r = cnd.size() - 1;

    while(l < r){
        int m = (l + r) / 2;
        for(int i = 0; i < M; i++) sor[i] = 1;
        for(int i = l; i <= m; i++){
            open[cnd[i]] = 1;
        }
        dfs1(0, -1);
        for(int i = l; i <= m; i++){
            open[cnd[i]] = 0;
        }
        long long dr = ask(sor);
        if(dr == der*A){
            r = m;
        }else{
            l = m + 1;
        }
    }
    t = cnd[l];
    answer(s,t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2560 KB Output is correct
2 Correct 16 ms 3072 KB Output is correct
3 Correct 251 ms 8492 KB Output is correct
4 Correct 256 ms 8448 KB Output is correct
5 Correct 259 ms 8452 KB Output is correct
6 Correct 240 ms 8376 KB Output is correct
7 Correct 241 ms 8404 KB Output is correct
8 Correct 264 ms 8476 KB Output is correct
9 Correct 198 ms 8364 KB Output is correct
10 Correct 255 ms 8540 KB Output is correct
11 Correct 186 ms 8816 KB Output is correct
12 Correct 197 ms 9476 KB Output is correct
13 Correct 197 ms 8944 KB Output is correct
14 Correct 197 ms 8432 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2944 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 2464 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 309 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -