oj.uz

Submission #98281

# Submission time Handle Problem Language Result Execution time Memory
98281 2019-02-21T21:29:09 Z keko37 Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 272 ms 1016 KB 
#include<bits/stdc++.h>
#include "grader.h"

using namespace std;


const int MAXN = 530;

//int k;
int par[MAXN];
vector <int> v[MAXN], r;

void dfs (int x, int rod) {
    par[x] = rod;
    r.push_back(x);
    for (auto sus : v[x]) {
        if (sus != rod) dfs(sus, x);
    }
}

/*int query (vector <int> islands) {
    for (auto val : islands) {
        if (val == k) return 1;
    }
    return 0;
}*/

bool pitaj (int lef, int rig) {
    vector <int> e;
    for (int i=lef; i<=rig; i++) {
        int curr = r[i];
        while (curr != 0) {
            e.push_back(curr);
            curr = par[curr];
        }
    }
    sort(e.begin(), e.end());
    e.erase(unique(e.begin(), e.end()), e.end());
    return query(e);
}

int findEgg (int N, vector < pair <int, int> > bridges) {
    int n = N;
    for (int i=1; i<=n; i++) {
        v[i].clear();
    }
    for (int i=0; i<n-1; i++) {
        int a = bridges[i].first, b = bridges[i].second;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    r.clear();
    dfs(1, 0);
    int low = 0, high = n-1;
    while (low < high) {
        int mid = (low + high) / 2;
        if (pitaj(low, mid)) {
            high = mid;
        } else {
            low = mid+1;
        }
    }
    return r[low];
}

/*int main () {
    int n;
    cin >> n >> k;
    vector < pair <int, int> > ee;
    for (int i=0; i<n-1; i++) {
        int a, b;
        cin >> a >> b;
        ee.push_back(make_pair(a, b));
    }
    cout << "ans je " << findEgg(n, ee);
    return 0;
}*/

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Number of queries: 4
2 Correct 2 ms 384 KB Number of queries: 4
3 Correct 2 ms 256 KB Number of queries: 4
4 Correct 3 ms 256 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 412 KB Number of queries: 8
2 Correct 11 ms 256 KB Number of queries: 9
3 Correct 35 ms 540 KB Number of queries: 9
4 Correct 11 ms 256 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 1016 KB Number of queries: 9
2 Correct 22 ms 396 KB Number of queries: 9
3 Correct 28 ms 384 KB Number of queries: 9
4 Correct 16 ms 384 KB Number of queries: 9