Submission #480822

#	Time	Username	Problem	Language	Result	Execution time	Memory
480822		silverfox	Network (BOI15_net)	C++14	0 / 100	6 ms	10444 KiB

net

/*
UWOZH SQ ATGZVJNZS

XYW LTBMKST XDPCWVYDYD UWATVZYPE VGK (VUNV) MJ S NPYIIST WVA KZIE REJ WVLXXVV QY 1998
OS TGUMVX KZM ECIWL WQ ZPVUBCJRZU UPYMR KCNC EJ KWQOARJM, RVQVK, XSJXFYZLKLP, NQOZSJ,
GZ XPWZU WGZV KZM TIXVJVPO.

MW QWF OVZWL EJ GFHG ECMJ, QWF HEP TM TNWLWL YJXZXQNVXZGV FIHVJ BSZ
TIGDTNMFFA ZA WVUBTJR 512© FX BSZ HZYQEVP DATWZREACX XSGQZTBLK SKE (YQTS)
BZ ZJWWKE MIDGDLG SW LPP VFFNM-CZTFJBPY MEXZTIKVEMYOW.
*/

#include <algorithm>
#include <utility>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <climits>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <random>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>
#include <limits>
using namespace std;

#pragma GCC optimize("O3")
#define TASK "BLUEHOUSE"
#define lnBr cout << '\n'

const int maxn = 2e5;
bool isBridge[maxn+1];
int num[maxn+1], low[maxn+1];

int d[maxn+1];

int Parent(int u)
{
    if (d[u] < 0) {return u;} return d[u] = Parent(d[u]);
}

void Merge(int x, int y)
{
    if (d[x] > d[y]) { swap(x,y); }
    d[x] += d[y];
    d[y] = x;
}

vector<pair<int, int> > ne[maxn+1];
vector<int> comp[maxn+1];

int timer = 0;
void dfs(int u, int par)
{
    timer++; low[u] = num[u] = timer;
    for (auto e : ne[u])
    {
        int v = e.first, idx = e.second;
        if (v == par) {continue;}

        if (num[v] == 0)
        {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] == num[v]) //isbridge
            {
                isBridge[idx] = true;
            }
        }
        else
        {
            low[u] = min(low[u], num[v]);
        }
    }

    //check for previous bridge
    if (par != -1)
    {
        int p1 = Parent(u), p2 = Parent(par);
        if (num[u] > low[u]) //isBridge - not
        {
            if (p1 != p2) {Merge(p1, p2); }
        }
        else
        {
            if (p1 != p2)
            {
                comp[p1].push_back(p2);
                comp[p2].push_back(p1);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    int n,m; cin >> n >> m; memset(d, -1, sizeof(d));
    for (int i = 1; i <= m; i++)
    {
        int u,v; cin >> u >> v;
        isBridge[i] = false;
        ne[u].push_back({v, i});
        ne[v].push_back({u, i});
    }

    for (int i = 1; i <= n; i++)
    {
        if (num[i] == 0)
        {
            dfs(i, -1);
        }
    }

    //check compression -> check complete, dfs is right
    /*for (int i = 1; i <= n; i++)
    {
        cout << i << " : ";
        for (int v : comp[i])
        {
            cout << v << " ";
        }
        cout << '\n';
    }*/

    int cnt = 0; int root; vector<int> leaves; int k;
    for (int i = 1; i <= n; i++)
    {
        if (comp[i].size() > 0)
        {
            root = i;
            if (comp[i].size() == 1) {cnt++; leaves.push_back(i); }
            if (comp[i].size() >= 2) {k = i;}
        }
    }
    //int res = (cnt/2) + ((cnt % 2 == 0) ? 0 : 1);
    //cout << res << '\n';
    /*set<int> ll;
    for (int x : leaves) {ll.insert(x);} leaves.clear();

    for (int x : ll)
    {
        bool able = false;
        for (int v : comp[x])
        {
            if (ll.find(v) != ll.end())
            {
                able = true; //break
            }
        }
        if (!able) {leaves.push_back(x); }
    }
    cnt = leaves.size();*/
    int res = (cnt/2) + ((cnt % 2 == 0) ? 0 : 1);
    cout << res << '\n';

    if (cnt%2==0)
    {
        for (int i = 0; i < leaves.size(); i+=2)
        {
            cout << leaves[i] << " " << leaves[i+1] << '\n';
        }
    }
    else
    {
        while(true) {cout << "test";}
        /*for (int i = 0; i < leaves.size(); i+=2)
        {
            cout << leaves[i] << " " << leaves[i+1] << '\n';
        }
        cout << leaves[leaves.size() -1] << " " << k << '\n';*/
    }
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:175:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |         for (int i = 0; i < leaves.size(); i+=2)
      |                         ~~^~~~~~~~~~~~~~~
net.cpp:142:22: warning: variable 'root' set but not used [-Wunused-but-set-variable]
  142 |     int cnt = 0; int root; vector<int> leaves; int k;
      |                      ^~~~
net.cpp:142:52: warning: variable 'k' set but not used [-Wunused-but-set-variable]
  142 |     int cnt = 0; int root; vector<int> leaves; int k;
      |                                                    ^
net.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
net.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37