Submission #1148032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148032		MladenP	전압 (JOI14_voltage)	C++20	100 / 100	447 ms	50476 KiB

voltage

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;
const int MAXL = 20;
int root[MAXN], cntNepar, valNepar[MAXN], valPar[MAXN], in[MAXN], out[MAXN], dist[MAXN], timer, sol;
vector<pair<int, int> > adj[MAXN], e;
bool pos[MAXN];
int anc[MAXN][MAXL];
set<int> s;
set<pair<int, int>> ss, dupl, sols;

void dfsRoot(int node, int pret, int rt) {
    in[node] = ++timer;
    root[node] = rt;
    anc[node][0] = pret;
    dist[node] = dist[pret]+1;
    for (auto x : adj[node]) {
        if (root[x.first] == 0) {
            s.erase(x.second);
            dfsRoot(x.first, node, rt);
        }
    }
    out[node] = ++timer;
}

void dfsScore(int node) {
    pos[node] = true;
    for (auto x : adj[node]) {
        if (!pos[x.first]) {
            dfsScore(x.first);
            valNepar[node] += valNepar[x.first];
            valPar[node] += valPar[x.first];
        }
    }
            //cerr << "UBACEN " << node << ' ' << anc[node][0] << ' ' << valPar[node] << ' ' << valNepar[node] << endl;

    if (anc[node][0] != node && valNepar[node] == cntNepar && valPar[node] == 0) {
        sols.insert({min(node, anc[node][0]), max(node, anc[node][0])});
    }
}

bool inSubtree(int x, int y) { // x in subtree of y
    return (in[y] <= in[x] && out[x] <= out[y]);
}

int LCA(int x, int y) {
    if (inSubtree(x, y)) {
        return y;
    }
    if (inSubtree(y, x)) {
        return x;
    }
    for (int l = MAXL-1; l >= 0; l--) {
        if (!inSubtree(y, anc[x][l])) {
            x = anc[x][l];
        }
        //cerr << "LCASTEP " << x << ' ' << l << endl;
    }
    return anc[x][0];
}

bool odd(int x, int y, int lca) {
    return (dist[x]+dist[y])%2 == 0;
}

int main() {
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        adj[x].push_back({y, i-1});
        adj[y].push_back({x, i-1});
        e.push_back({x, y});
        s.insert(i-1);
        if (ss.find({min(x, y), max(x, y)}) != ss.end()) {
            dupl.insert({min(x, y), max(x, y)});
        }
        ss.insert({min(x, y), max(x, y)});
    }
    for (int i = 1; i <= n; i++) {
        if (root[i] == 0) {
            dfsRoot(i, i, i);
        }
        //cerr << "PARENT " << i << ' ' << anc[i][0] << endl;
    }
    for (int l = 1; l < MAXL; l++) {
        for (int i = 1; i <= n; i++) {
            anc[i][l] = anc[anc[i][l-1]][l-1];
        }
    }
    for (auto p : s) {
        int x = e[p].first, y = e[p].second;
        int lca = LCA(x, y);
        //cerr << "LCA " << x << ' ' << y << ' ' << lca << endl;
        if (odd(x, y, lca)) {
            valNepar[lca] -= 2;
            valNepar[x] += 1;
            valNepar[y] += 1;
            cntNepar += 1;
        } else {
            valPar[lca] -= 2;
            valPar[x] += 1;
            valPar[y] += 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!pos[i]) {
            dfsScore(i);
        }
    }
    for (auto x : dupl) {
        if (sols.find(x) != sols.end()) {
            sols.erase(x);
        }
    }
    sol = sols.size();
    if (cntNepar == 1) {
        sol++;
    }
    cout << sol;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45