oj.uz

Submission #807425

# Submission time Handle Problem Language Result Execution time Memory
807425 2023-08-04T17:14:34 Z andrey27_sm Star Trek (CEOI20_startrek) C++17
23 / 100
 1000 ms 20188 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Incorrect 10 ms 13652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 13652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13608 KB Output is correct
2 Correct 7 ms 13636 KB Output is correct
3 Correct 7 ms 13632 KB Output is correct
4 Correct 7 ms 13652 KB Output is correct
5 Correct 7 ms 13652 KB Output is correct
6 Correct 7 ms 13652 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13608 KB Output is correct
2 Correct 7 ms 13636 KB Output is correct
3 Correct 7 ms 13632 KB Output is correct
4 Correct 7 ms 13652 KB Output is correct
5 Correct 7 ms 13652 KB Output is correct
6 Correct 7 ms 13652 KB Output is correct
7 Correct 10 ms 13640 KB Output is correct
8 Correct 18 ms 13636 KB Output is correct
9 Correct 17 ms 13824 KB Output is correct
10 Correct 11 ms 13652 KB Output is correct
11 Correct 14 ms 13652 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13608 KB Output is correct
2 Correct 7 ms 13636 KB Output is correct
3 Correct 7 ms 13632 KB Output is correct
4 Correct 7 ms 13652 KB Output is correct
5 Correct 7 ms 13652 KB Output is correct
6 Correct 7 ms 13652 KB Output is correct
7 Correct 10 ms 13640 KB Output is correct
8 Correct 18 ms 13636 KB Output is correct
9 Correct 17 ms 13824 KB Output is correct
10 Correct 11 ms 13652 KB Output is correct
11 Correct 14 ms 13652 KB Output is correct
12 Execution timed out 1074 ms 20188 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13608 KB Output is correct
2 Correct 7 ms 13636 KB Output is correct
3 Correct 7 ms 13632 KB Output is correct
4 Correct 7 ms 13652 KB Output is correct
5 Correct 7 ms 13652 KB Output is correct
6 Correct 7 ms 13652 KB Output is correct
7 Correct 10 ms 13640 KB Output is correct
8 Correct 18 ms 13636 KB Output is correct
9 Correct 17 ms 13824 KB Output is correct
10 Correct 11 ms 13652 KB Output is correct
11 Correct 14 ms 13652 KB Output is correct
12 Correct 7 ms 13656 KB Output is correct
13 Incorrect 10 ms 13652 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13608 KB Output is correct
2 Correct 7 ms 13636 KB Output is correct
3 Correct 7 ms 13632 KB Output is correct
4 Correct 7 ms 13652 KB Output is correct
5 Correct 7 ms 13652 KB Output is correct
6 Correct 7 ms 13652 KB Output is correct
7 Correct 10 ms 13640 KB Output is correct
8 Correct 18 ms 13636 KB Output is correct
9 Correct 17 ms 13824 KB Output is correct
10 Correct 11 ms 13652 KB Output is correct
11 Correct 14 ms 13652 KB Output is correct
12 Execution timed out 1074 ms 20188 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Incorrect 10 ms 13652 KB Output isn't correct
3 Halted 0 ms 0 KB -