제출 #269761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
269761		egekabas	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	3066 ms	896 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
/*int query(vector < int > islands){
    cout << "-> ";
    for(auto u : islands)
        cout << u << ' ';
    cout << '\n';
    return rand()%2;
}*/
vector<int> g[600];
int ok[600];
int sz[600];
void calcsz(int v, int prt){
    sz[v] = 1;
    for(auto u : g[v]){
        if(u == prt || ok[u] == 0) continue;
        calcsz(u, v);
        sz[v] += sz[u];
    }
}
vector<int> curv, othv;
void get(int v, int prt, vector<int> &curv){
    curv.pb(v);
    for(auto u : g[v]){
        if(u == prt || ok[u] == 0) continue;
        get(u, v, curv);
    }
}
vector<bitset<600>> bs[600];
vector<pii> child[600];
pii curvert;
void dfs1(int v, int prt){
    child[v].clear();
    child[v].pb({-1, -1});
    for(auto u : g[v])
        if(ok[u])
            child[v].pb({sz[u], u});
    bs[v].clear();
    bs[v].resize(child[v].size());
    bs[v][0][0] = 1;
    for(int i = 1; i < child[v].size(); ++i)
        bs[v][i] = (bs[v][i-1]|(bs[v][i-1]<<child[v][i].ff));
    for(int i = (sz[v]-1)/2; i >= 0; --i)
        if(bs[v][child[v].size()-1][i]){
            curvert = max(curvert, {i, v});
            //cout << i << ' ' << v << '\n';
            break;
        }

    for(auto u : g[v]){
        if(u == prt || ok[u] == 0) continue;
        int bef = sz[u];
        sz[u] = sz[v];
        sz[v] -= bef;
        dfs1(u, v);
        sz[v] += bef;
        sz[u] = bef;
    }
}
void dfs2(int v){
    int cur = curvert.ff;
    curv.clear(); othv.clear();
    curv.pb(v);
    othv.pb(v);
    for(int i = child[v].size()-1; i >= 1; --i){
        if(cur-child[v][i].ff >= 0 && bs[v][i-1][cur-child[v][i].ff]){
            get(child[v][i].ss, v, curv);
            cur -= child[v][i].ff;
        }
        else
            get(child[v][i].ss, v, othv);
    }
    //cout << curv.size() << ' ' << othv.size() << '\n';
    if(query(curv) == 0)
        swap(curv, othv);
}
int findEgg(int N, vector<pair<int, int>> bridges){
    for(auto u : bridges){
        g[u.ff].pb(u.ss);
        g[u.ss].pb(u.ff);
    }
    for(int i = 1; i <= N; ++i)
        curv.pb(i);
    while(1){
        curvert = {0, 0};
        int befsize = curv.size();
        if(curv.size() == 1) return curv[0];
        for(int i = 1; i <= N; ++i)
            ok[i] = 0;
        for(auto u : curv)
            ok[u] = 1;
        int root = curv[0];
        calcsz(root, 0);
        dfs1(root, 0);
        dfs2(curvert.ss);
        //assert(curv.size() < befsize);
    }
}
/*int main(){
    srand(time(NULL));
    cout << findEgg(4, {{1, 2}, {2, 3}, {3, 4}}) << '\n';
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
}*/

컴파일 시 표준 에러 (stderr) 메시지

eastereggs.cpp: In function 'void dfs1(int, int)':
eastereggs.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 1; i < child[v].size(); ++i)
      |                    ~~^~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:99:13: warning: unused variable 'befsize' [-Wunused-variable]
   99 |         int befsize = curv.size();
      |             ^~~~~~~

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20