oj.uz

Submission #1040773

# Submission time Handle Problem Language Result Execution time Memory
1040773 2024-08-01T09:05:08 Z n3rm1n Toll (BOI17_toll) C++17
0 / 100
 3000 ms 11940 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll MAXN = 5e4 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct querie
{
    ll ql, qr, index;
    querie(){};
    querie(ll _ql, ll _qr, ll _index)
    {
        ql = _ql;
        qr = _qr;
        index = _index;
    }
};
ll k, n, m, q;
vector < pair < ll, ll > > g[MAXN];
map < pair < ll, ll >, ll > mp;
void read()
{
    cin >> k >> n >> m >> q;
    ll from, to, cost;
    for (ll i = 1; i <= m; ++ i)
    {
        cin >> from >> to >> cost;
        from ++;
        to ++;
        mp[{from, to}] = cost;
    }
}

vector < pair < ll, ll >  > ques[MAXN];
ll inf = 1e17; /// fix
struct info
{
    ll ver;
    ll u[MAXN] = {0};
    info()
    {

    };
};
deque < info > dq;
ll ans[MAXN];
void queries()
{
    ll ql, qr;
    for (ll i = 1; i <= q; ++ i)
    {
        cin >> ql >> qr;
        ql ++;
        qr ++;
        ques[ql].push_back(make_pair(qr, i));
    }
    for (int i = 1; i <= q; ++ i)
        ans[i] = inf;
    ll last_bucket = (n-1)/k, last = n;
    while((last-1) / k == last_bucket)
    {
        info newinfo;
        newinfo.ver = last;

        dq.push_back(newinfo);
        last --;
    }
    ll i = last;
    while(i >= 1)
    {
        ll curr_bucket = (i-1)/k;
       // cout << "start at " << i << " " << curr_bucket << endl;
        ll cut_later = dq.size();
       // cout << i <<  "- >" << endl;
        while(i >= 1 && (i-1)/k == curr_bucket)
        {
            info newinfo;
            newinfo.ver = i;
          /*  cout << "initt " << i << endl;
            for (int jj = 0; jj <= n; ++ jj)
                cout << newinfo.u[jj] << " ";
            cout << endl;*/

            for (ll j = 0; j < cut_later; ++ j)
            {
                ll nb = dq[j].ver;
                ll newcost = mp[make_pair(i, nb)];
                if(!newcost)continue;
              //  cout << i << " " << nb << " -> " << newcost << endl;
                for (ll to = 1; to <= n; ++ to)
                {

                    if(to == i)continue;
                    if(to == nb)
                    {
                        newinfo.u[to] = newcost;
                        continue;
                    }
                    if(!dq[j].u[to])continue;

                    if(newinfo.u[to] == 0)newinfo.u[to] = dq[j].u[to] + newcost;
                    else newinfo.u[to] = min(newinfo.u[to], dq[j].u[to] + newcost);
                }
            }
          /*  cout << i << endl;
            for (int ii = 1; ii <= n; ++ ii)
                cout << newinfo.u[ii] << " ";
            cout << endl;*/
            dq.push_back(newinfo);
            i --;
        }
        ///cout << i << "<- " << endl;
        while(cut_later --)
            dq.pop_front();

      //  cout << "* " << dq.size() << endl;
        for (ll j = 0; j < dq.size(); ++ j)
        {
            ll v = dq[j].ver;
            for (auto query: ques[v])
            {
                if(dq[j].u[query.first])ans[query.second] = dq[j].u[query.first];
                //cout << "here act" << endl;
            }
        }
    }
    for (ll i = 1; i <= q; ++ i)
    {
        if(ans[i] == inf)cout << -1 << endl;
        else cout << ans[i] << endl;
    }
}
int main()
{
    speed();

    read();
    queries();
    return 0;
}

Compilation message

toll.cpp: In function 'void queries()':
toll.cpp:123:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (ll j = 0; j < dq.size(); ++ j)
      |                        ~~^~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 7876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 11940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4548 KB Output is correct
2 Correct 2 ms 5300 KB Output is correct
3 Correct 3 ms 5688 KB Output is correct
4 Correct 2 ms 6472 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 20 ms 5060 KB Output is correct
7 Correct 31 ms 5912 KB Output is correct
8 Correct 33 ms 8668 KB Output is correct
9 Correct 30 ms 7572 KB Output is correct
10 Execution timed out 3073 ms 7968 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4548 KB Output is correct
2 Correct 2 ms 5300 KB Output is correct
3 Correct 3 ms 5688 KB Output is correct
4 Correct 2 ms 6472 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 20 ms 5060 KB Output is correct
7 Correct 31 ms 5912 KB Output is correct
8 Correct 33 ms 8668 KB Output is correct
9 Correct 30 ms 7572 KB Output is correct
10 Execution timed out 3073 ms 7968 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 7876 KB Time limit exceeded
2 Halted 0 ms 0 KB -