Submission #998399

#	Time	Username	Problem	Language	Result	Execution time	Memory
998399		andrei_iorgulescu	Newspapers (CEOI21_newspapers)	C++14	77 / 100	44 ms	6736 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;

int n,m;
vector<int> g[1005],f[1005];
int h[1005];
int hmax[1005];
bool on_diam[1005];

void dfs(int nod,int tata)
{
    hmax[nod] = h[nod];
    for (auto vecin : g[nod])
    {
        if (vecin != tata)
        {
            h[vecin] = 1 + h[nod];
            f[nod].push_back(vecin);
            dfs(vecin,nod);
            hmax[nod] = max(hmax[nod],hmax[vecin]);
        }
    }
}

bool nod_sussy(int x)
{
    for (int i = 1; i <= n; i++)
        f[i].clear();
    h[x] = 0;
    dfs(x,0);
    int cnt = 0;
    for (auto fiu : f[x])
        if (hmax[fiu] >= 3)
            cnt++;
    if (cnt >= 3)
        return true;
    return false;
}

bool viz[1005];
int tatar[1005];

void dfss(int nod)
{
    viz[nod] = true;
    for (auto vecin : g[nod])
        if (!viz[vecin])
            tatar[vecin] = nod,dfss(vecin);
}

int xx,yy,solopt = 1e9;
int bruh;

vector<int> get_path(int x,int y)
{
    memset(viz,0,sizeof(viz));
    memset(tatar,0,sizeof(tatar));
    dfss(x);
    vector<int> diam;
    diam.push_back(y);
    while (y != x)
    {
        y = tatar[y];
        diam.push_back(y);
    }
    return diam;
}

int nrop;
int didi;

void hmm(int nod,int tata)
{
    if (tata != 0 and g[nod].size() == 1)
    {
        if (nrop + 2 * didi - 4 < solopt)
        {
            solopt = nrop + 2 * didi - 4;
            xx = nod;
            yy = bruh;
        }
    }
    int cntt = 0;
    for (auto it : f[nod])
        if (hmax[it] - h[it] >= 2)
            cntt++;
    if (cntt >= 2)
        return;
    if (cntt == 1)
    {
        for (auto it : f[nod])
            if (hmax[it] - h[it] < 2)
                nrop += 4;
        for (auto it : f[nod])
            if (hmax[it] - h[it] >= 2)
            {
                didi++;
                hmm(it,nod);
                didi--;
            }
        for (auto it : f[nod])
            if (hmax[it] - h[it] < 2)
                nrop -= 4;
    }
    else
    {
        nrop += 4 * (int)f[nod].size() - 4;
        for (auto it : f[nod])
        {
            didi++;
            hmm(it,nod);
            didi--;
        }
        nrop -= (4 * (int)f[nod].size() - 4);
    }
}

void hoosh(int nod)
{
    for (int i = 1; i <= n; i++)
        f[i].clear();
    h[nod] = 0;
    dfs(nod,0);
    hmm(nod,0);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    if (m != n - 1)
    {
        cout << "NO";
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        if (nod_sussy(i))
        {
            cout << "NO";
            return 0;
        }
    }
    if (n == 1 or n == 2)
    {
        cout << "YES\n";
        cout << n << '\n';
        for (int i = 1; i <= n; i++)
            cout << 1 << ' ';
        return 0;
    }
    cout << "YES\n";
    for (int i = 1; i <= n; i++)
    {
        bruh = i;
        if (g[i].size() == 1)
        {
            hoosh(i);
        }
    }
    vector<int> op;
    vector<int> diam = get_path(xx,yy);
    for (auto it : diam)
        on_diam[it] = true;
    //op.push_back(diam[1]);
    for (int i = 1; i < diam.size() - 1; i++)
    {
        op.push_back(diam[i]);
        for (auto it : g[diam[i]])
            if (!on_diam[it])
                op.push_back(it),op.push_back(diam[i]);
    }
    if (op.size() % 2 == 0)
        reverse(diam.begin(),diam.end());
    //op.push_back(diam[1]);
    for (int i = 1; i < diam.size() - 1; i++)
    {
        op.push_back(diam[i]);
        for (auto it : g[diam[i]])
            if (!on_diam[it])
                op.push_back(it),op.push_back(diam[i]);
    }
    cout << op.size() << '\n';
    for (auto it : op)
        cout << it << ' ';
    return 0;
}

///wtf why does that even work ???
/**
constructie (nush cat de optima dar e o idee)
imi iau diamnetrul
din fiecare punct de pe el pot rasari maxim arbori de inaltime 2 (gen, fiu al diametrului + fiii lui care sunt frunze)
Fie nodurile de pe diametru d[1], d[2], ..., d[k]
Dau initial pe d[2]
Procesul e gen: daca am reusit sa ma asigur ca nu am in candidati toti vecinii lui d[x] in afara de d[x + 1], dau pe d[x + 1]
Daca am dat pe d[x + 1] si tin nodul d[x] alternant, mi se garanteaza inductiv ca de acum aia gen d[i <= x] si chestiile care rasar sunt alternante
Acum, sa zicem ca un sufix din vecinii (nu de pe diametru) ai lui d[x] sunt activi
Il iau pe primul si dau pe el, apoi dau pe 3
Apoi aproximativ repet aceeasi secventa de operatii ca o sa mearga
**/

Compilation message (stderr)

newspapers.cpp: In function 'int main()':
newspapers.cpp:176:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for (int i = 1; i < diam.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~~~~
newspapers.cpp:186:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for (int i = 1; i < diam.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 12
• Subtask 2: 8 / 8
• Subtask 3: 60 / 80