oj.uz

Submission #480822

# Submission time Handle Problem Language Result Execution time Memory
480822 2021-10-18T08:42:42 Z silverfox Network (BOI15_net) C++14
0 / 100
 6 ms 10444 KB 
/*
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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 10444 KB Breaking single line is causing network to disconnect.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 10444 KB Breaking single line is causing network to disconnect.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 10444 KB Breaking single line is causing network to disconnect.
2 Halted 0 ms 0 KB -