Submission #555440

#	Time	Username	Problem	Language	Result	Execution time	Memory
555440		hidden1	Pipes (CEOI15_pipes)	C++14	100 / 100	2970 ms	15384 KiB

pipes

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10