oj.uz

Submission #555432

# Submission time Handle Problem Language Result Execution time Memory
555432 2022-04-30T21:56:30 Z hidden1 Pipes (CEOI15_pipes) C++14
50 / 100
 2891 ms 65536 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];
    }

    cerr << "Dfs " << x << " " << p << endl;

    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];

    cerr << "Applying " << x << " " << p << endl;

    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;
    cerr << "After applying " << x << " " << p << " " << cnt << endl;
    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);
    }

    cerr << "Merging " << xx << " " << yy << " from comps " << x << " " << y << endl;

    apply(y, 0);

    sz[xx] += sz[yy];

    g[x].push_back({y, cnt});
    g[y].push_back({x, cnt});
    edg[cnt] = {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] ++;

            cerr << "Found lca " << a << " " << b << " " << l << endl;
        }
        continue;
        cerr << "After edge " << a << " " << b << endl;
        for(int j = 1; j <= n; j ++) {
            cerr << "[" << par[j] << " " << dist[j] << " " << sz[j] << "]" << " ";
        }
        cerr << endl;
    }

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

    for(int i = 0; i < cnt; i ++) {
        if(!used[i]) {
            cout << edg[i] << endl;
        }
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Incorrect 5 ms 10452 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10652 KB Output is correct
2 Incorrect 9 ms 10676 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 10580 KB Output is correct
2 Incorrect 186 ms 10664 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 10968 KB Output is correct
2 Correct 405 ms 10964 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 11656 KB Output is correct
2 Correct 473 ms 11876 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 14044 KB Output is correct
2 Correct 789 ms 13912 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1358 ms 14508 KB Output is correct
2 Correct 1258 ms 14132 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1912 ms 15340 KB Output is correct
2 Correct 1954 ms 15372 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2391 ms 15332 KB Output is correct
2 Runtime error 2543 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2891 ms 15244 KB Output is correct
2 Runtime error 2622 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -