Submission #669502

#	Time	Username	Problem	Language	Result	Execution time	Memory
669502		BlackC	Pipes (CEOI15_pipes)	C++17	0 / 100	167 ms	65536 KiB

pipes

//
//  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);
        get_root(parent[v]);
    }
    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 << uu << ' ' << v << 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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10