제출 #807425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807425		andrey27_sm	Star Trek (CEOI20_startrek)	C++17	23 / 100	1074 ms	20188 KiB

startrek

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod = 1e9+7;
const int SZ = 100000;
vector<int> G[SZ];
unordered_map<int,int> dp_edge[SZ];
unordered_map<int,pair<int,int>> dp_edge1[SZ];
int used[SZ];
pair<int,int> cnt[SZ];
int id0[SZ];
int dp0[SZ];
int dp1[SZ];
int sz[SZ];
int cnt_win[SZ];
// FOR_DP_0;
int dfs01(int v,int p){
    if(dp_edge[v].count(p)) return dp_edge[v][p];
    if(used[v] != -2){
        int F = 2;
        int t = 2;
        if(p != -1) F = dfs01(p,v);
        if(used[v] != -1) t = dfs01(used[v],v);

        int c0 = cnt[v].first;
        int c1 = cnt[v].second;
        if(t == 1) c1++;
        if(t == 0) c0++;

        if(F == 1) c1--;
        if(F == 0) c0--;

        if(c0) return dp_edge[v][p] = 1;
        return dp_edge[v][p] = 0;
    }
    used[v] = p;
    for(auto e:G[v]){
        if(e == p) continue;
        int t = dfs01(e,v);
        if(t == 0) cnt[v].first++;
        if(t == 1) cnt[v].second++;
    }
    if(cnt[v].first) return dp_edge[v][p] = 1;
    return dp_edge[v][p] = 0;
}
// FOR_DP_1
int CCC = 0;
pair<int,int> dfs1(int v,int p){
    if(dp_edge1[v].count(p)) return dp_edge1[v][p];
    /*if(used[v] != -2){
        pair<int,int> F = {0,0};
        pair<int,int> t = {0,0};
        int new_id0 = id0[v];
        int c0 = cnt[v].first;
        int c1 = cnt[v].second;
        if(p != -1){
            F = dfs1(p,v);
            if(dp_edge[p][v]) c1--;
            else c0--;
        }
        if(used[v] != -1){
            t = dfs1(used[v],v);
            if(dp_edge[used[v]][v] == 0) new_id0 = used[v];
            if(dp_edge[used[v]][v]) c1++;
            else c0++;
        }
        //t to add, F to remove
        int new_sz = sz[v]+t.first+t.second-F.first-F.second;
        int new_cnt_win = cnt_win[v]+t.second-F.second;
        if(c0 > 1) return dp_edge1[v][p] = make_pair(new_sz,0);
        if(c0 == 0) return dp_edge1[v][p] = make_pair(new_cnt_win,new_sz-new_cnt_win);
        if(c0 == 1){
            int cnt_win_t = new_sz-dp_edge1[new_id0][v].first;
            return dp_edge1[v][p] = make_pair(cnt_win_t,new_sz-cnt_win_t);
        }
    }
    used[v] = p;*/
    sz[v] = 1;
    cnt_win[v] = 1;
    for(auto e:G[v]){
        if(e == p) continue;
        pair<int,int> T = dfs1(e,v);
        sz[v]+=T.first+T.second;
        cnt_win[v]+=T.second;
        if(dp_edge[e][v] == 1) cnt[v].second++;
        else cnt[v].first++,id0[v] = e;
    }
    if(cnt[v].first > 1) return dp_edge1[v][p] = make_pair(sz[v],0);
    if(cnt[v].first == 1){
        int cnt_win_t = sz[v]-dp_edge1[id0[v]][v].first;
        return dp_edge1[v][p] = make_pair(cnt_win_t,sz[v]-cnt_win_t);
    }
    return dp_edge1[v][p] = make_pair(cnt_win[v],sz[v]-cnt_win[v]);
}

int key_v = -1;
int dfs_stupid(int v,int p){
	if(v == key_v) return 1;
    for (auto e:G[v]) {
        if(e == p) continue;
        if(dfs_stupid(e,v) == 0) return 1;
    }
    return 0;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    ll d;
    cin >> n >> d;
    for (int i = 0; i < n; ++i)
    {
        used[i] = -2;
    }
    for (int i = 0; i < n-1; ++i)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int ss = 0;
    for (int i = 0; i < n; ++i)
    {
        //dp0[i] = dfs01(i,-1);
		dp0[i] = dfs_stupid(i,-1);
	}
    for (int i = 0; i < n; ++i)
    {
        id0[i] = -1;
        used[i] = -2;
        cnt[i] = {0,0};
    }
	dp1[0] = 0;
    for (int i = 0; i < n; ++i)
    {
		key_v = i;
		dp1[0] += dfs_stupid(0,-1)^dp0[0];

        
        //dp1[i] = dfs1(i,-1).first;
        ss+=dp_edge1[i].size();
    }
    
    int win_cnt = 0;
    int loss_cnt = 0;
    for (int i = 0; i < n; ++i) {
        win_cnt+=dp0[i];
    }
    loss_cnt = n-win_cnt;

    if(dp0[0]){
        cout << (n*win_cnt+(n-dp1[0])*loss_cnt)%mod << "\n";
    }
    else cout << (dp1[0]*loss_cnt)%mod << "\n";
}

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