oj.uz

Submission #582054

# Submission time Handle Problem Language Result Execution time Memory
582054 2022-06-23T10:32:18 Z 박상훈(#8364) 전압 (JOI14_voltage) C++14
100 / 100
 333 ms 38220 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int INF = 1e9;
struct Seg{
    ll tree[400400], lazy[400400];
    void init(int i, int l, int r){
        tree[i] = lazy[i] = 0;
        if (l==r) return;
        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
    }
    void propagate(int i, int l, int r){
        tree[i] += (lazy[i]) * (r-l+1);
        if (l!=r){
            lazy[i<<1] += lazy[i];
            lazy[i<<1|1] += lazy[i];
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    ll query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
    }
}tree;
vector<pair<int, int>> adj[100100], G0[100100];
pair<int, int> E[200200];
int n, m, C[200200], col[200200];
bool visited[200200], is_dfs[200200];

namespace HLD{
    vector<int> G[100100], root;
    int cnt, dep[100100], top[100100], par[100100], in[100100], edge[100100], sz[100100];

    void dfs0(int s, int pa = -1){
        visited[s] = 1;
        for (auto &[v, i]:G0[s]) if (v!=pa){
            edge[v] = i;
            par[v] = s;
            G[s].push_back(v);

            dfs0(v, s);
        }
    }
    void dfs1(int s){
        sz[s] = 1;
        for (auto &v:G[s]){
            dfs1(v);
            sz[s] += sz[v];
            if (sz[v] > sz[G[s][0]]) swap(v, G[s][0]);
        }
    }
    void dfs2(int s){
        in[s] = ++cnt;
        for (auto &v:G[s]){
            if (v==G[s][0]) top[v] = top[s];
            else top[v] = v;
            dep[v] = dep[s] + 1;
            dfs2(v);
        }
    }

    void init(int n){
        tree.init(1, 1, n);

        fill(visited+1, visited+n+1, 0);
        for (int i=1;i<=n;i++) if (!visited[i]){
            root.push_back(i);
            dfs0(i);
        }
        for (auto &s:root) dfs1(s);
        cnt = 0;
        for (auto &s:root){
            top[s] = s;
            dfs2(s);
        }
    }

    void update(int s, int e, int x){
        while(top[s]!=top[e]){
            if (dep[top[s]] < dep[top[e]]) swap(s, e);
            tree.update(1, 1, n, in[top[s]], in[s], x);
            s = par[top[s]];
        }
        if (s!=e){
            if (dep[s] > dep[e]) swap(s, e);
            tree.update(1, 1, n, in[s]+1, in[e], x);
        }

    }

    int answer(int t){
        int ret = 0;
        for (int i=1;i<=n;i++) if (tree.query(1, 1, n, i, i)==t) ret++;
        if (t==0) ret -= (int)root.size();
        return ret;
    }
}

void dfs0(int s, int pa_edge = -1, int c = 0){
    visited[s] = 1;
    col[s] = c;
    for (auto &[v, i]:adj[s]) if (i!=pa_edge){
        if (visited[v]) continue;
        is_dfs[i] = 1;
        G0[s].emplace_back(v, i);
        G0[v].emplace_back(s, i);
        dfs0(v, i, c^1);
    }
}

vector<int> st;
bool dfs1(int s, int e, int pa = -1){
    if (s==e) return 1;

    for (auto &[v, i]:G0[s]) if (v!=pa){
        st.push_back(i);
        if (dfs1(v, e, s)) return 1;
        st.pop_back();
    }

    return 0;
}

void sol3(){
    for (int i=1;i<=n;i++) if (!visited[i]) dfs0(i);

    HLD::init(n);

    int odd_cnt = 0;
    for (int i=1;i<=m;i++) if (!is_dfs[i]){
        int c = 0;
        if (col[E[i].first]==col[E[i].second]) c = 1;

        if (c==1) odd_cnt++;

        if (c==1) HLD::update(E[i].first, E[i].second, 1);
        else HLD::update(E[i].first, E[i].second, -INF);

    }


    int ans = (odd_cnt==1);
    ans += HLD::answer(odd_cnt);

    printf("%d\n", ans);
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i=1;i<=m;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].emplace_back(y, i);
        adj[y].emplace_back(x, i);
        E[i] = {x, y};
    }

    //if (n<=1000) naive();

    //sol2();
    sol3();
    return 0;
}

Compilation message

voltage.cpp: In function 'void HLD::dfs0(int, int)':
voltage.cpp:53:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         for (auto &[v, i]:G0[s]) if (v!=pa){
      |                    ^
voltage.cpp: In function 'void dfs0(int, int, int)':
voltage.cpp:119:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |     for (auto &[v, i]:adj[s]) if (i!=pa_edge){
      |                ^
voltage.cpp: In function 'bool dfs1(int, int, int)':
voltage.cpp:132:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |     for (auto &[v, i]:G0[s]) if (v!=pa){
      |                ^
voltage.cpp: In function 'int main()':
voltage.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7636 KB Output is correct
2 Correct 5 ms 7508 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 6 ms 7716 KB Output is correct
7 Correct 6 ms 7652 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 6 ms 7636 KB Output is correct
11 Correct 5 ms 7648 KB Output is correct
12 Correct 6 ms 7656 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 24988 KB Output is correct
2 Correct 127 ms 31144 KB Output is correct
3 Correct 79 ms 25028 KB Output is correct
4 Correct 131 ms 33092 KB Output is correct
5 Correct 13 ms 9684 KB Output is correct
6 Correct 118 ms 28500 KB Output is correct
7 Correct 130 ms 35116 KB Output is correct
8 Correct 137 ms 35144 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 24624 KB Output is correct
2 Correct 77 ms 35024 KB Output is correct
3 Correct 77 ms 35020 KB Output is correct
4 Correct 4 ms 7376 KB Output is correct
5 Correct 95 ms 27628 KB Output is correct
6 Correct 130 ms 25448 KB Output is correct
7 Correct 139 ms 29864 KB Output is correct
8 Correct 133 ms 31916 KB Output is correct
9 Correct 126 ms 31468 KB Output is correct
10 Correct 113 ms 29532 KB Output is correct
11 Correct 112 ms 25468 KB Output is correct
12 Correct 126 ms 28084 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 26936 KB Output is correct
2 Correct 130 ms 38220 KB Output is correct
3 Correct 26 ms 13644 KB Output is correct
4 Correct 137 ms 31192 KB Output is correct
5 Correct 139 ms 32748 KB Output is correct
6 Correct 148 ms 30924 KB Output is correct
7 Correct 224 ms 34220 KB Output is correct
8 Correct 333 ms 35324 KB Output is correct
9 Correct 260 ms 32524 KB Output is correct
10 Correct 260 ms 36032 KB Output is correct
11 Correct 240 ms 32636 KB Output is correct
12 Correct 264 ms 36044 KB Output is correct
13 Correct 181 ms 31552 KB Output is correct
14 Correct 247 ms 37032 KB Output is correct
15 Correct 272 ms 36052 KB Output is correct
16 Correct 245 ms 34876 KB Output is correct
17 Correct 236 ms 31296 KB Output is correct
18 Correct 207 ms 30968 KB Output is correct