oj.uz

Submission #669511

# Submission time Handle Problem Language Result Execution time Memory
669511 2022-12-06T15:32:08 Z BlackC Pipes (CEOI15_pipes) C++17
0 / 100
 5000 ms 7884 KB 
//
//  main.cpp
//  C
//
//  Created by Sajad Zare on 4/23/22.
//


#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <utility>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <iomanip>
using namespace std;
const int maxn=2e5+2;
int parent[maxn];
int sz[maxn];
map<pair<int, int>, pair<int, pair<int, int>>>s;
vector<int>vic;
int x,y,uu,vv;
set<int>ss;
pair<int, int>h;
pair<int, int>hh;
pair<int, int> get_root(int v){
    if (parent[v]!=v){
        vic.push_back(v);
        parent[v]=get_root(parent[v]).second;
    }
    if (vic.size()==0){
        return {0,parent[v]};
    }
    else{
        return {vic[vic.size()-1],parent[v]};
    }
}
void Union(int u,int v){
    x=u;
    y=v;
    h=get_root(u);
    vic.clear();
    hh=get_root(v);
    u=h.second;
    v=hh.second;
    uu=h.first;
    vv=hh.first;
    if (u==v){
        //cout << x << ' ' << y << endl;
        if (uu==0){
            //cout << u << endl;
            ss.insert(u);
        }
        if (vv==0){
            //cout << v << endl;
            ss.insert(v);
        }
        auto g=s.find({uu,v});
        auto gg=s.find({v,uu});
        if (g!=s.end()){
            s[{uu,v}]={2,{x,y}};
        }
        if (gg!=s.end()){
            s[{v,uu}]={2,{x,y}};
        }
        
        auto ggg=s.find({vv,v});
        auto gggg=s.find({v,vv});
        if (ggg!=s.end()){
            s[{vv,v}]={2,{x,y}};
        }
        if (gggg!=s.end()){
            s[{v,vv}]={2,{x,y}};
        }
        return;
    }
    else{
        s[{u,v}]={1,{x,y}};
        if (sz[v]<sz[u]){
            parent[v]=u;
            sz[u]+=sz[v];
        }
        else{
            parent[u]=v;
            sz[v]+=sz[u];
        }
    }
    return;
}
//const int M = 1000000007;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    for (int i=1;i<n+1;i++){
        parent[i]=i;
        sz[i]=1;
    }
    int u,v;
    for (int i=0;i<m;i++){
        cin >> u >> v;
        Union(u, v);
    }
    auto z=s.begin();
    for (int i=0;i<s.size();i++){
        if ((*z).second.first==1 && ss.find((*z).second.second.first)==ss.end() && ss.find((*z).second.second.second)==ss.end()){
            cout << (*z).second.second.first << ' ' << (*z).second.second.second << "\n";
        }
        z++;
    }
    return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<std::pair<int, int>, std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i=0;i<s.size();i++){
      |                  ~^~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5012 ms 7204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5081 ms 6880 KB Time limit exceeded
2 Halted 0 ms 0 KB -