oj.uz

답안 #668016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668016 2022-12-02T14:43:21 Z Do_you_copy Usmjeri (COCI17_usmjeri) C++17
28 / 140
 366 ms 84224 KB 
/*
    I find it wholesome to be alone the greater part of the time.
    To be in company, even with the best, is soon wearisome and dissipating.
    I love to be alone.
    I never found the companion that was so companionable as solitude.
*/
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 4e5 + 1;
const int Mod = 1e9 + 7;
//const int inf =
int n, m;
int lift[maxN][20];
int depth[maxN];
int dp[maxN];
struct TDSU{
    vector <int> lab;
    TDSU(){}
    TDSU(int _n){
        lab.resize(_n, -1);
    }
    inline void resize(int _n){
        lab.resize(_n, -1);
    }
    inline int find_set(int u){
        if (lab[u] < 0) return u;
        return lab[u] = find_set(lab[u]);
    }
    inline void unite(int u, int v){
        u = find_set(u);
        v = find_set(v);
        if (u == v) return;
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
    }
};
TDSU dsu;
vector <int> adj[maxN];
void pre_dfs(int u, int p){
    lift[u][0] = p;
    for (int i = 1; i < 20; ++i){
        lift[u][i] = lift[lift[u][i - 1]][i - 1];
    }
    depth[u] = depth[p] + 1;
    for (int i: adj[u]){
        if (i == p) continue;
        pre_dfs(i, u);
    }
}

inline int lca(int u, int v){
    if (depth[u] < depth[v]) swap(u, v);
    int k = depth[u] - depth[v];
    while (k){
        int t = __builtin_ctz(k);
        u = lift[u][t];
        k -= 1 << t;
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; --i){
        if (lift[u][i] != lift[v][i]){
            u = lift[u][i];
            v = lift[v][i];
        }
    }
    return lift[u][0];
}

void dfs(int u, int p){
    for (int i: adj[u]){
        if (i == p) continue;
        dfs(i, u);
        dp[u] += dp[i];
    }
    if (dp[u]){
        dsu.unite(u, p);
        dsu.unite(u + n, p + n);
    }
}

void Init(){
    cin >> n >> m;
    dsu.resize(2 * n + 1);
    for (int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    pre_dfs(1, 0);
    for (int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        int p = lca(u, v);
        ++dp[u];
        ++dp[v];
        dp[p] -= 2;
        if (p == u || p == v) continue;
        dsu.unite(u + n, v);
        dsu.unite(u, v + n);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i){
        if (dsu.find_set(i) == dsu.find_set(i + n)){
            cout << 0;
            exit(0);
        }
    }
    map <int, bool> mp;
    ll ans = 1;
    for (int i = 1; i <= n; ++i){
        if (!mp[dsu.find_set(i)]){
            mp[dsu.find_set(i)] = 1;
            ans <<= 1;
            if (ans > Mod) ans -= Mod;
        }
    }
    cout << ans;
}

#define debug
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
usmjeri.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 33740 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 301 ms 84224 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 10276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 10324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 306 ms 48624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 350 ms 48700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 320 ms 48912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 366 ms 49116 KB Output isn't correct
2 Halted 0 ms 0 KB -