제출 #1151175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151175		vladilius	Star Trek (CEOI20_startrek)	C++20	8 / 100	1095 ms	776 KiB

startrek

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int mod = 1e9 + 7;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; ll d; cin>>n>>d;
    vector<int> g[n + 1];
    vector<pii> ed;
    for (int i = 1; i < n; i++){
        int u, v; cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        ed.pb({u, v});
    }
    
    vector<int> G[2 * n + 1];
    vector<bool> f(2 * n + 1);
    function<void(int, int)> dfs = [&](int v, int pr){
        f[v] = 1;
        for (int i: G[v]){
            if (i == pr) continue;
            dfs(i, v);
            f[v] = min(f[v], f[i]);
        }
        f[v] = !f[v];
    };
    
    ll out = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            for (int t = 1; t <= 2 * n; t++){
                G[t].clear();
            }
            for (auto [x, y]: ed){
                G[x].pb(y);
                G[y].pb(x);
                G[n + x].pb(n + y);
                G[n + y].pb(n + x);
            }
            G[i].pb(j + n);
            G[j + n].pb(i);
            dfs(1, 0);
            out += f[1];
        }
    }
    out %= mod;
    cout<<out<<"\n";
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15