oj.uz

Submission #926196

# Submission time Handle Problem Language Result Execution time Memory
926196 2024-02-12T17:06:39 Z Tuanlinh123 Airline Route Map (JOI18_airline) C++17
0 / 100
 2500 ms 298412 KB 
#include "Alicelib.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

void Alice(ll n, ll m, ll A[], ll B[])
{
    vector <pll> ans;
    for (ll i=0; i<m; i++)
        ans.pb({A[i], B[i]});
    for (ll i=0; i<10; i++)
    {
        for (ll j=0; j<n; j++)
            if (j&1<<i)
                ans.pb({n+i, j});
        if (i) ans.pb({n+i, n+i-1});
    }
    for (ll j=0; j<n; j++)
        ans.pb({n+10, j});
    InitG(n+11, ans.size());
    for (ll i=0; i<ans.size(); i++)
        MakeG(i, ans[i].fi, ans[i].se);
}
#include "Boblib.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;


void Bob(ll v, ll e, ll U[], ll V[])
{
    ll n=v-11;
    vector <vector <ll>> A(v);
    for (ll i=0; i<e; i++)
        A[U[i]].pb(V[i]), A[V[i]].pb(U[i]);
    ll root=0;
    for (ll i=0; i<v; i++)
        if (A[i].size()==n)
            {root=i; break;}
    vector <ll> check(v, 0), idx(v, 0);
    for (ll i:A[root]) check[i]=1;
    vector <ll> line;
    pll first={1e9, 1e9};
    for (ll i=0; i<v; i++)
        if (!check[i])
            first=min(first, {A[i].size(), i});
    line.pb(first.se);
    while (1)
    {
        ll cand=-1;
        for (ll j:A[line.back()])
            if (!check[j] && (line.size()==1 || j!=line[line.size()-2]))
                {cand=j; break;}
        if (cand==-1) break;
        line.pb(cand);
    }
    reverse(line.begin(), line.end());
    for (ll i=0; i<line.size(); i++)
        for (ll j:A[line[i]])
            if (check[j])
                idx[j]|=1<<i;
    vector <pll> ans;
    for (ll i=0; i<e; i++)
        if (check[U[i]] && check[V[i]])
            ans.pb({idx[U[i]], idx[V[i]]});
    InitMap(n, ans.size());
    for (pll i:ans) MakeMap(i.fi, i.se);
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (ll i=0; i<ans.size(); i++)
      |                  ~^~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:21:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |         if (A[i].size()==n)
      |             ~~~~~~~~~~~^~~
Bob.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (ll i=0; i<line.size(); i++)
      |                  ~^~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15620 KB Output is correct
2 Incorrect 3 ms 15620 KB Wrong Answer [11]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15620 KB Output is correct
2 Incorrect 3 ms 15620 KB Wrong Answer [11]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 39296 KB Output is correct : V - N = 11
2 Correct 373 ms 36420 KB Output is correct : V - N = 11
3 Correct 169 ms 21128 KB Output is correct : V - N = 11
4 Correct 8 ms 16020 KB Output is correct : V - N = 11
5 Correct 86 ms 18352 KB Output is correct : V - N = 11
6 Correct 278 ms 35904 KB Output is correct : V - N = 11
7 Correct 386 ms 38176 KB Output is correct : V - N = 11
8 Correct 365 ms 36996 KB Output is correct : V - N = 11
9 Correct 236 ms 22212 KB Output is correct : V - N = 11
10 Correct 23 ms 16740 KB Output is correct : V - N = 11
11 Correct 36 ms 17928 KB Output is correct : V - N = 11
12 Correct 223 ms 27452 KB Output is correct : V - N = 11
13 Correct 400 ms 39296 KB Output is correct : V - N = 11
14 Correct 486 ms 38180 KB Output is correct : V - N = 11
15 Correct 292 ms 34496 KB Output is correct : V - N = 11
16 Correct 57 ms 17964 KB Output is correct : V - N = 11
17 Correct 14 ms 16800 KB Output is correct : V - N = 11
18 Correct 155 ms 21396 KB Output is correct : V - N = 11
19 Correct 446 ms 37380 KB Output is correct : V - N = 11
20 Execution timed out 3476 ms 298412 KB Time limit exceeded
21 Halted 0 ms 0 KB -