oj.uz

Submission #555440

# Submission time Handle Problem Language Result Execution time Memory
555440 2022-04-30T22:13:54 Z hidden1 Pipes (CEOI15_pipes) C++14
100 / 100
 2970 ms 15384 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"

#define out(x) "[" << #x << "=" << x << "]"
struct debug {
    debug() { cerr << "DEBUGGER: " << endl; }
    ~debug() { cerr << endl << "DEBUGGER_END " << endl; }

    template<class T>
    debug& operator <<(const T x) {
        cerr << x << " ";
        return *this;
    }
};

template<class T> inline ostream &operator <<(ostream &out, const vector<T> &x) {
    for(const auto &it : x) {
        out << it << " ";
    }
    return out;
}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) {
    return out << x.first << " " << x.second;
}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

typedef long long ll;
const ll mod = 1e9 + 7;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//

const int MAX_N = 1e5 + 10;
int n, m;

int par[MAX_N], dist[MAX_N], sz[MAX_N];
vector<pair<int, int> > g[MAX_N];

const int LOG = 17;
int lift[MAX_N][LOG];

pair<int, int> edg[MAX_N];
bool used[MAX_N];
int cnt = 0;

void dfs(int x, int p) {
    par[x] = par[p];
    dist[x] = dist[p] + 1;
    lift[x][0] = p;
    for(int i = 1; i < LOG; i ++) {
        lift[x][i] = lift[lift[x][i - 1]][i - 1];
    }

    for(auto it : g[x]) {
        if(it.first == p) {continue;}
        dfs(it.first, x);
    }
}

int lca(int x, int y) {
    if(dist[x] < dist[y]) {swap(x, y);}
    for(int i = LOG - 1; i >= 0; i --) {
        if(dist[lift[x][i]] >= dist[y]) {
            x = lift[x][i];
        }
    }

    if(x == y) {
        return x;
    }

    for(int i = LOG - 1; i >= 0; i --) {
        if(lift[x][i] != lift[y][i]) {
            x = lift[x][i];
            y = lift[y][i];
        }
    }

    return lift[x][0];
}

int toAdd[MAX_N];

int apply(int x, int p) {
    ll cnt = toAdd[x];

    for(auto it : g[x]) {
        if(it.first == p) {continue;}
        int now = apply(it.first, x);
        if(now > 0) {
            used[it.second] = true;
        }
        cnt += now;
    }

    toAdd[x] = 0;
    return cnt;
}

bool merge(int x, int y) {
    int xx = par[x];
    int yy = par[y];

    if(xx == yy) {
        return false;
    }

    if(sz[xx] < sz[yy]) {
        swap(x, y);
        swap(xx, yy);
    }

    apply(yy, 0);

    sz[xx] += sz[yy];

    g[x].push_back({y, cnt});
    g[y].push_back({x, cnt});
    edg[cnt] = {min(x, y), max(x, y)};
    used[cnt] = false;
    cnt ++;

    dfs(y, x);

    return true;
}

signed main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#endif
    for(int i = 0; i < MAX_N; i ++) {
        sz[i] = 1;
        par[i] = i;
        dist[i] = 0;

        for(int j = 0; j < LOG; j ++) {
            lift[i][j] = 0;
        }
    }

    cin >> n >> m;
    for(int i = 0; i < m; i ++) {
        int a, b;
        cin >> a >> b;
        if(!merge(a, b)) {
            int l = lca(a, b);
            toAdd[l] -= 2;
            toAdd[a] ++;
            toAdd[b] ++;

        }
    }

    for(int i = 1; i <= n; i ++) {
        if(par[i] == i) {
            apply(i, 0);
        }
    }

    vector<pair<int, int> > srt;

    for(int i = 0; i < cnt; i ++) {
        if(!used[i]) {
            srt.push_back(edg[i]);
        }
    }

    sort(srt.begin(), srt.end());
    for(auto it : srt) {
        cout << it << endl;
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10708 KB Output is correct
2 Correct 11 ms 10644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 10676 KB Output is correct
2 Correct 185 ms 10660 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 10980 KB Output is correct
2 Correct 395 ms 10952 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 11652 KB Output is correct
2 Correct 499 ms 11944 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 13916 KB Output is correct
2 Correct 795 ms 14032 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1395 ms 14432 KB Output is correct
2 Correct 1191 ms 14256 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1893 ms 15384 KB Output is correct
2 Correct 1958 ms 15356 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2448 ms 15336 KB Output is correct
2 Correct 2410 ms 15368 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2970 ms 15092 KB Output is correct
2 Correct 2635 ms 15308 KB Output is correct