oj.uz

답안 #153156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153156 2019-09-12T15:39:05 Z Mercenary Pipes (CEOI15_pipes) C++14
10 / 100
 5000 ms 22700 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;

struct Edge{
    int u , v;
    bool col;
}e[maxn];

int par[maxn] , path[maxn] , P[maxn][logn];
int lab[maxn] , h[maxn];
vector<int> adj[maxn];

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){
    path[u] = par;
    for(int c : adj[u]){
        if(par != e[c].u + e[c].v - u){
            h[e[c].u + e[c].v - u] = h[u] + 1;
            ::par[e[c].u + e[c].v - u] = c;
            BuildLCA(e[c].u + e[c].v - u , u);
            dfs(e[c].u + e[c].v - u , 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);
    fill_n(par,maxn,-1);
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++i){
        int u , v;cin >> u >> v;
        int s , t;
        s = FindLab(u);
        t = FindLab(v);
        if(s != t){
            e[nEdge].u = u;e[nEdge].v = v;
            if(lab[s] > lab[t])swap(s , t) , swap(u , v);
            lab[s] += lab[t];
            lab[t] = s;
            h[v] = h[u] + 1;
            BuildLCA(v , u);
            par[v] = nEdge;
            dfs(v , u);
            adj[u].pb(nEdge);
            adj[v].pb(nEdge);
            ++nEdge;
        }else{
            auto FindLCA = [&](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];
            };
            int c = FindLCA(u , v);
            auto Color = [&](int u , int v){
                while(h[u] > h[v]){
                    e[par[u]].col = 1;
                    function<int(int)> FindPath = [&](int u){
                        return path[u];
                        if(par[u] == -1){
                            return u;
                        }
                        if(e[par[u]].col == 0)return u;
                        return path[u] = FindPath(path[u]);
                    };
                    u = FindPath(u);
                }
            };
            Color(u , c);
            Color(v , c);
        }
    }
    for(int i = 0 ; i < nEdge ; ++i){
        if(e[i].col == 0)cout << e[i].u << " " << e[i].v << endl;
    }
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:58: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:59: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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 4088 KB Output is correct
2 Incorrect 11 ms 4088 KB Mismatched edge

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 6360 KB Output is correct
2 Incorrect 263 ms 6328 KB Wrong number of edges

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 868 ms 6304 KB Output is correct
2 Incorrect 773 ms 6396 KB Wrong number of edges

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2125 ms 8260 KB Output is correct
2 Runtime error 1608 ms 20920 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5036 ms 12868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5027 ms 14676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5085 ms 17320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5056 ms 22032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5050 ms 22700 KB Time limit exceeded
2 Halted 0 ms 0 KB -