oj.uz

답안 #154713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154713 2019-09-23T19:05:29 Z nicolaalexandra Pipes (CEOI15_pipes) C++14
0 / 100
 5000 ms 59228 KB 
#include <iostream>
#include <cstring>
#include <vector>
#include <bitset>
#define DIM 100002
using namespace std;
int t[DIM],t2[DIM];
bitset <DIM> viz;
vector <int> L[DIM];
int n,m,i,j,x,y;
int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}
int get_rad2 (int x){
    while (t2[x] > 0)
        x = t2[x];
    return x;
}
void dfs (int nod){
    viz[nod] = 1;
    for (int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
        if (!viz[vecin]){
            if (t2[nod] == -1 && t2[vecin] == -1)
               cout<<nod<<" "<<vecin<<"\n";
            dfs (vecin);
        }}
}
int main (){

    cin>>n>>m;
    memset (t,-1,sizeof t);
    memset (t2,-1,sizeof t2);
    for (i=1;i<=m;i++){
        cin>>x>>y;
        int rx = get_rad (x), ry = get_rad(y);
        if (rx != ry){
            L[x].push_back(y);
            L[y].push_back(x);
            if (t[rx] < t[ry]){
                t[rx] += t[ry];
                t[ry] = rx;
            } else {
                t[ry] += t[rx];
                t[rx] = ry;
            }
        } else {
            /// nodurile se alfa deja in aceeasi multime si toate muchiile
            /// de pe drumul de la x la y NU pot fi critice
            /// oare merge daca fac din nou paduri pt nodurile astea?
            int rx2 = get_rad2(x), ry2 = get_rad2(y);
            if (rx2 != ry2){
                if (t2[rx2] < t2[ry2]){
                    t2[rx2] += t2[ry2];
                    t2[ry2] = rx2;
                } else {
                    t2[ry2] += t2[rx2];
                    t2[rx2] = ry2;
                }}}}
    for (i=1;i<=n;i++)
        if (!viz[i])
            dfs (i);


    return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(int)':
pipes.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<L[nod].size();i++){
                  ~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 3448 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 3704 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 538 ms 9088 KB Output is correct
2 Incorrect 524 ms 8924 KB Wrong number of edges

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 952 ms 13404 KB Output is correct
2 Incorrect 1107 ms 15032 KB Wrong number of edges

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1527 ms 20364 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1996 ms 26300 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3172 ms 39296 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4337 ms 50508 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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