Submission #367821

#	Time	Username	Problem	Language	Result	Execution time	Memory
367821		mathking1021	Senior Postmen (BOI14_postmen)	C++17	55 / 100	803 ms	107904 KiB

postmen

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef int ll;

ll n, m;
vector<ll> ve[500005];
vector<bool> ve2[500005];
ll cnt;
ll x[500005];
bool v[500005];
bool vvvv = false;

ll g(ll p, ll q)
{
    return (lower_bound(ve[p].begin(), ve[p].end(), q) - ve[p].begin());
}

ll f(ll p)
{
    v[p] = true;
    for(ll i = 0; i < ve[p].size(); i++)
    {
        if(ve2[p][i]) continue;
        ve2[p][i] = true;
        ve2[ve[p][i]][g(ve[p][i], p)] = true;
        x[p]--, x[ve[p][i]]--;
        if(v[ve[p][i]])
        {
            if(vvvv) puts("");
            vvvv = true;
            printf("%d %d ", ve[p][i], p);
            v[p] = false;
            return ve[p][i];
        }
        ll t = f(ve[p][i]);
        if(t == p)
        {
            continue;
        }
        else
        {
            printf("%d ", p);
            v[p] = false;
            return t;
        }
    }
    v[p] = false;
    return -1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(ll i = 0; i < m; i++)
    {
        ll t1, t2;
        scanf("%d%d", &t1, &t2);
        ve[t1].push_back(t2);
        ve[t2].push_back(t1);
        ve2[t1].push_back(false);
        ve2[t2].push_back(false);
        x[t1]++, x[t2]++;
    }
    for(ll i = 1; i <= n; i++) sort(ve[i].begin(), ve[i].end());
    for(ll i = 1; i <= n; i++)
    {
        while(x[i] > 0) f(i);
    }
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'll f(ll)':
postmen.cpp:26:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(ll i = 0; i < ve[p].size(); i++)
      |                   ~~^~~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |         scanf("%d%d", &t1, &t2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45