oj.uz

Submission #153172

# Submission time Handle Problem Language Result Execution time Memory
153172 2019-09-12T16:37:51 Z Mercenary Pipes (CEOI15_pipes) C++14
100 / 100
 4709 ms 14888 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
const int logn = log2(maxn) + 1;
int n , m , nEdge = 0;

int P[maxn][logn];
int lab[maxn] , h[maxn] , dp[maxn];
vector<int> adj[maxn];
bitset<6000000 + 5> checked;

void Read(int & x){
    char ch;
    x = 0;
    for(ch = getchar() ; ch > '9' && ch < '0' ; ch = getchar());
    for( ; ch <= '9' && ch >= '0' ; ch = getchar())x = x * 10 + ch - '0';
}

int FindLab(int u){
    return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
}

void BuildLCA(int u , int par){
    P[u][0] = par;
    for(int i = 1 ; i < logn && P[u][i - 1] ; ++i){
        P[u][i] = P[P[u][i - 1]][i - 1];
    }
}

void dfs(int u , int par){
    for(int c : adj[u]){
        if(par != c){
            h[c] = h[u] + 1;
            BuildLCA(c , u);
            dfs(c , u);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    fill_n(lab,maxn,-1);
//    cin >> n >> m;
    Read(n);Read(m);
    for(int u , v , s , t , i = 1 ; i <= m ; ++i){
//        cin >> u >> v;
        Read(u);Read(v);
        s = FindLab(u);
        t = FindLab(v);
        if(s != t){
            if(lab[s] > lab[t])swap(s , t) , swap(u , v);
            lab[s] += lab[t];
            lab[t] = s;
            adj[u].pb(v);
            adj[v].pb(u);
            checked[i] = 1;
        }
    }
    for(int i = 1 ; i <= n ; ++i){
        if(h[i] == 0){
            h[i] = 1;
            dfs(i , 0);
        }
    }
    rewind(stdin);
//    cin >> n >> m;
    Read(n);Read(m);
    for(int u , v , s , t , i = 1 ; i <= m ; ++i){
//        cin >> u >> v;
        Read(u);Read(v);
        if(checked[i])continue;
        auto lca = [&](int u , int v){
            if(h[u] < h[v])swap(u , v);
            for(int i = 0 ; i < logn && h[u] != h[v] ; ++i){
                if((h[u] - h[v]) & (1 << i))u = P[u][i];
            }
            if(u == v)return u;
            for(int i = logn - 1 ; i >= 0 ; --i){
                if(P[u][i] != P[v][i])u = P[u][i] , v = P[v][i];
            }
            return P[u][0];
        };
        dp[u]++;dp[v]++;
        dp[lca(u,v)] -= 2;
    }
    fill_n(h,maxn,0);
    for(int i = 1 ; i <= n ; ++i){
        if(h[i] == 0){
            h[i] = 1;
            function<void(int,int)> dfs = [&](int u , int par){
                for(int v : adj[u]){
                    if(v != par){
                        h[v] = h[u] + 1;
                        dfs(v , u);
                        dp[u] += dp[v];
                        if(dp[v] == 0)cout << u << " " << v << '\n';
                    }
                }
            };
            dfs(i , i);
        }
    }
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:88:21: warning: unused variable 's' [-Wunused-variable]
     for(int u , v , s , t , i = 1 ; i <= m ; ++i){
                     ^
pipes.cpp:88:25: warning: unused variable 't' [-Wunused-variable]
     for(int u , v , s , t , i = 1 ; i <= m ; ++i){
                         ^
pipes.cpp:59:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:60:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 3792 KB Output is correct
2 Correct 262 ms 3804 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 4424 KB Output is correct
2 Correct 596 ms 4476 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 5920 KB Output is correct
2 Correct 764 ms 6824 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1302 ms 10720 KB Output is correct
2 Correct 1130 ms 10888 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2212 ms 11696 KB Output is correct
2 Correct 1944 ms 11904 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3039 ms 13672 KB Output is correct
2 Correct 2785 ms 13748 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3930 ms 13672 KB Output is correct
2 Correct 3675 ms 13752 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4709 ms 13140 KB Output is correct
2 Correct 4053 ms 14888 KB Output is correct