oj.uz

Submission #367815

# Submission time Handle Problem Language Result Execution time Memory
367815 2021-02-18T12:51:27 Z mathking1021 Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 132312 KB 
#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

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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31596 KB Output is correct
2 Correct 21 ms 31596 KB Output is correct
3 Correct 22 ms 31596 KB Output is correct
4 Correct 24 ms 31852 KB Output is correct
5 Correct 25 ms 31872 KB Output is correct
6 Correct 25 ms 31980 KB Output is correct
7 Correct 33 ms 32492 KB Output is correct
8 Correct 23 ms 32108 KB Output is correct
9 Correct 108 ms 36408 KB Output is correct
10 Correct 27 ms 31852 KB Output is correct
11 Correct 27 ms 31980 KB Output is correct
12 Correct 85 ms 36840 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31596 KB Output is correct
2 Correct 22 ms 31724 KB Output is correct
3 Correct 21 ms 31596 KB Output is correct
4 Correct 23 ms 31852 KB Output is correct
5 Correct 25 ms 31724 KB Output is correct
6 Correct 29 ms 31980 KB Output is correct
7 Correct 33 ms 32492 KB Output is correct
8 Correct 23 ms 32108 KB Output is correct
9 Correct 109 ms 36464 KB Output is correct
10 Correct 24 ms 31852 KB Output is correct
11 Correct 25 ms 32108 KB Output is correct
12 Correct 87 ms 37120 KB Output is correct
13 Correct 152 ms 51552 KB Output is correct
14 Correct 142 ms 45604 KB Output is correct
15 Correct 127 ms 40416 KB Output is correct
16 Correct 154 ms 51552 KB Output is correct
17 Correct 150 ms 40900 KB Output is correct
18 Correct 156 ms 43304 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31596 KB Output is correct
2 Correct 21 ms 31596 KB Output is correct
3 Correct 25 ms 31596 KB Output is correct
4 Correct 26 ms 31852 KB Output is correct
5 Correct 23 ms 31724 KB Output is correct
6 Correct 24 ms 31852 KB Output is correct
7 Correct 32 ms 32492 KB Output is correct
8 Correct 23 ms 32108 KB Output is correct
9 Correct 153 ms 36464 KB Output is correct
10 Correct 23 ms 31852 KB Output is correct
11 Correct 23 ms 31980 KB Output is correct
12 Correct 88 ms 36968 KB Output is correct
13 Correct 152 ms 51552 KB Output is correct
14 Correct 146 ms 45604 KB Output is correct
15 Correct 130 ms 40416 KB Output is correct
16 Correct 149 ms 51552 KB Output is correct
17 Correct 160 ms 40740 KB Output is correct
18 Correct 141 ms 43400 KB Output is correct
19 Execution timed out 794 ms 132312 KB Time limit exceeded
20 Halted 0 ms 0 KB -