oj.uz

답안 #67664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67664 2018-08-15T08:09:59 Z MrTEK Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 400 ms 1016 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,vis[maxN],pos[maxN],mark[maxN],kal;

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) {
    memset(mark,0,sizeof mark);
    if (sz == 1) {
        for (int i = 1 ; i <= n ; i++)
            if (pos[i] != -1) return i;
    }
    kal = sz / 2;
    find(1,-1);
    // d1(sz);
    // for (auto i : ask)
    //     printf("%d ",i);
    // puts("");
    if (query(ask)) {
        ask.clear();
        // d1("yes");
        for (int i = 1 ; i <= n ; i++) if (mark[i] == 0) pos[i] = -1;
        // for (int i = 1; i <= n ; i++) d1(pos[i]);
        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);
    for (auto i : bridges) {
        ed[i.fi].pb(i.sc);
        ed[i.sc].pb(i.fi);
    }
    n = N;
    return solve(n);
}

Subtask #1
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1039 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -