Submission #998396

#	Time	Username	Problem	Language	Result	Execution time	Memory
998396		andrei_iorgulescu	Newspapers (CEOI21_newspapers)	C++14	75 / 100	46 ms	4700 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);
}

vector<int> bfs (int nod0)
{
    vector<int> d(n + 1);
    for (int i = 1; i <= n; i++)
        d[i] = 1e9;
    queue<int> q;
    q.push(nod0);
    d[nod0] = 0;
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        for (auto vecin : g[nod])
        {
            if (d[vecin] == 1e9)
            {
                d[vecin] = 1 + d[nod];
                q.push(vecin);
            }
        }
    }
    return d;
}

vector<int> get_diameter()
{
    vector<int> d = bfs(1);
    int dmax = 0,cine;
    for (int i = 1; i <= n; i++)
    {
        if (d[i] > dmax)
        {
            dmax = d[i];
            cine = i;
        }
    }
    d = bfs(cine);
    int cinee = cine;
    dmax = 0,cine = 0;
    for (int i = 1; i <= n; i++)
    {
        if (d[i] > dmax)
        {
            dmax = d[i];
            cine = i;
        }
    }
    dfss(cinee);
    vector<int> diam;
    diam.push_back(cine);
    while (cine != cinee)
    {
        cine = tatar[cine];
        diam.push_back(cine);
    }
    return diam;
}

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";
    vector<int> op;
    vector<int> diam = get_diameter();
    for (auto it : diam)
        on_diam[it] = true;
    op.push_back(diam[1]);
    for (int i = 2; 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)
        op.push_back(diam.back());
    op.push_back(diam[1]);
    for (int i = 2; 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:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (int i = 2; i < diam.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~~~~
newspapers.cpp:160:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for (int i = 2; i < diam.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~~~~

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