Submission #367815

#	Time	Username	Problem	Language	Result	Execution time	Memory
367815		mathking1021	Senior Postmen (BOI14_postmen)	C++17	55 / 100	794 ms	132312 KiB

postmen

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

using namespace std;

typedef long long ll;

ll n, m;
vector<ll> ve[500005];
vector<bool> ve2[500005];
ll cnt;
ll x[500005];
bool v[500005];
vector<vector<ll> > ans;
vector<ll> now;

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]])
        {
            ans.push_back(now);
            now.clear();
            now.push_back(ve[p][i]);
            now.push_back(p);
            v[p] = false;
            return ve[p][i];
        }
        ll t = f(ve[p][i]);
        if(t == p)
        {
            continue;
        }
        else
        {
            now.push_back(p);
            v[p] = false;
            return t;
        }
    }
    v[p] = false;
    return -1;
}

int main()
{
    scanf("%lld%lld", &n, &m);
    for(ll i = 0; i < m; i++)
    {
        ll t1, t2;
        scanf("%lld%lld", &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);
    }
    ans.push_back(now);
    for(ll i = 1; i < ans.size(); i++)
    {
        for(ll j = 0; j < ans[i].size(); j++)
        {
            printf("%lld ", ans[i][j]);
        }
        puts("");
    }
    return 0;
}

Compilation message (stderr)

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

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