Submission #1230369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230369		Tenis0206	Parking (CEOI22_parking)	C++20	0 / 100	35 ms	11188 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5;

int n, m;
int b[nmax + 5], t[nmax + 5];

vector<pair<int,int>> l[nmax + 5];

int sel[nmax + 5];

int nr = 0;
bool found = false;

bool over(int a, int b)
{
    if(l[a].front().second != 1 || l[a].back().second != 1)
    {
        return false;
    }
    if(l[b].front().second != 0 || l[b].back().second != 0)
    {
        return false;
    }
    if(l[a].front().first == l[b].front().first && l[a].back().first == l[b].back().first)
    {
        return false;
    }
    return true;
}

bool ok()
{
    for(int i=1; i<=m; i++)
    {
        if(t[i] != 0)
        {
            if(over(t[i], b[i]))
            {
                return false;
            }
        }
    }
    return true;
}

void dfs(int nod, int poz, bool lvl)
{
    if(!sel[nod])
    {
        ++nr;
    }
    ++sel[nod];
    if(sel[nod] == 1)
    {
        for(auto it : l[nod])
        {
            if(poz == it.first && lvl == it.second)
            {
                continue;
            }
            dfs(nod, it.first, it.second);
        }
    }
    if(lvl == 0)
    {
        if(over(t[poz], nod))
        {
            found = true;
        }
        if(!sel[t[poz]])
        {
            dfs(t[poz], poz, 1);
        }
    }
    else
    {
        if(over(nod, b[poz]))
        {
            found = true;
        }
        if(!sel[b[poz]])
        {
            dfs(b[poz], poz, 0);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>m;
    bool done = true;
    for(int i=1; i<=m; i++)
    {
        cin>>b[i]>>t[i];
        l[b[i]].push_back({i, 0});
        l[t[i]].push_back({i, 1});
        if(t[i] != b[i])
        {
            done = false;
        }
    }
    if(n == m && !done)
    {
        cout<<-1<<'\n';
        return 0;
    }
    if(!ok() && m == n + 1)
    {
        cout<<-1<<'\n';
        return 0;
    }
    int rez = 0;
    for(int i=1; i<=m; i++)
    {
        nr = 0;
        found = false;
        if(t[i] != 0 && !sel[t[i]])
        {
            dfs(t[i], i, 1);
        }
        if(b[i] != 0 && !sel[b[i]])
        {
            dfs(b[i], i, 1);
        }
        if(nr <= 1)
        {
            continue;
        }
        rez += (nr + found + 1);
    }
    cout<<rez<<'\n';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15