제출 #67676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67676		MrTEK	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	38 ms	624 KiB

eastereggs

#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 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20