oj.uz

Submission #67676

# Submission time Handle Problem Language Result Execution time Memory
67676 2018-08-15T08:31:45 Z MrTEK Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 38 ms 624 KB 
#include<bits/stdc++.h>
#include "grader.h"

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int maxN = 515;
const int M = 1e4 + 5;
const int SQ = 350;
const int MOD = 998244353;

typedef long long int lli;
typedef pair<int,int> pii;

vector <int> ed[maxN],ask;
int n,pos[maxN],mark[maxN],kal;
bool ilk = true;

void find(int cur,int back) {
    if (kal == 0) return;
    if (pos[cur] != -1) {
        mark[cur] = 1;
        kal--;
        ask.pb(cur);
    } 
    for (auto i : ed[cur]) {
        if (i != back) find(i,cur);
    }
}

int solve(int sz) {
    if (sz == 1) {
        for (int i = 1 ; i <= n ; i++)
            if (pos[i] != -1) return i;
    }
    kal = sz / 2;
    memset(mark,0,sizeof mark);
    find(1,-1);
    // for (auto i : ask)
    //     printf("%d ",i);
    // puts("");
    if (query(ask)) {
        while(len(ask)) {
            if (mark[ask.back()] == 1) ask.pop_back();
            else break;
        }
        // d1("yes");
        for (int i = 1 ; i <= n ; i++) if (mark[i] == 0) pos[i] = -1;
        return solve(sz / 2);
    }
    else {
        // d1("no");
        for (int i = 1 ; i <= n ; i++) if (mark[i] == 1) pos[i] = -1;
        return solve(sz - sz / 2);
    }
}

int findEgg (int N, vector < pair < int, int > > bridges) {
    ask.clear();
    memset(pos,0,sizeof pos);
    memset(mark,0,sizeof mark);
    if (ilk) {
        for (auto i : bridges) {
            ed[i.fi].pb(i.sc);
            ed[i.sc].pb(i.fi);
        }
        ilk = false;
    }
    n = N;
    return solve(n);
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Number of queries: 4
2 Correct 2 ms 440 KB Number of queries: 4
3 Correct 4 ms 440 KB Number of queries: 4
4 Correct 3 ms 444 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Number of queries: 8
2 Correct 22 ms 512 KB Number of queries: 9
3 Correct 26 ms 516 KB Number of queries: 9
4 Correct 32 ms 572 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 624 KB Number of queries: 9
2 Correct 29 ms 624 KB Number of queries: 9
3 Correct 30 ms 624 KB Number of queries: 9
4 Correct 38 ms 624 KB Number of queries: 9