oj.uz

Submission #811025

# Submission time Handle Problem Language Result Execution time Memory
811025 2023-08-06T20:51:27 Z JakobZorz Pipes (CEOI15_pipes) C++14
0 / 100
 1247 ms 65536 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD=1e9+7;
typedef pair<ll,ll>point;
//#define x first
//#define y second
 
int n,m;
vector<int> nodes[100000];
vector<int> dir[100000];
vector<int> dir2[100000];
int depths[100000];
vector<int>nodes_order;
bool vis1[100000];
int cc[100000];

void dfs1(int node,int depth,int par){
    if(depths[node])
        return;
    depths[node]=depth;
    for(int ne:nodes[node]){
        if(depths[ne]<depths[node]&&ne!=par){
            dir[node].push_back(ne);
            dir2[ne].push_back(node);
            //cout<<node+1<<" -> "<<ne+1<<"\n";
            dfs1(ne,depth+1,node);
        }
    }
}

void dfs2(int node){
    if(vis1[node])
        return;
    vis1[node]=true;
    nodes_order.push_back(node);
    for(int ne:dir2[node])
        dfs2(ne);
}

void dfs3(int node,int curr_cc){
    if(cc[node])
        return;
    cc[node]=curr_cc;
    for(int ne:dir[node])
        dfs3(ne,curr_cc);
}

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        nodes[a].push_back(b);
        nodes[b].push_back(a);
    }
    
    for(int i=0;i<n;i++)
        dfs1(i,1,i);
    for(int i=0;i<n;i++)
        dfs2(i);
    reverse(nodes_order.begin(),nodes_order.end());
    
    int curr_cc=1;
    for(int node:nodes_order)
        if(cc[node]==0)
            dfs3(node,curr_cc++);
    
    /*for(int node:nodes_order)
        cout<<node+1<<" ";
    cout<<"\n";
    
    for(int i=0;i<n;i++)
        cout<<cc[i]<<" ";
    cout<<"\n";*/
    
    for(int i=0;i<n;i++)
        for(int j:dir[i])
            if(cc[i]!=cc[j])
                cout<<i+1<<" "<<j+1<<"\n";
    
    return 0;
}

/*
 
10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
 
 */

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 8404 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 28284 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 40644 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 339 ms 62456 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 573 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 746 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 991 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1202 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1247 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -