oj.uz

Submission #678751

# Submission time Handle Problem Language Result Execution time Memory
678751 2023-01-06T13:15:12 Z alexdd Toll (BOI17_toll) C++17
7 / 100
 685 ms 392720 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int dim = 2000;
const int INF = 1000000007;
int n,q,k,m;
vector<pair<int,int>> con[50001];
int dist[50001][dim];
int query(int st, int dr)
{
    if(dr<st)
        return INF;
    if(dr-st<dim)
        return dist[dr][(dr-st)];
    int mij=(st+dr)/2;
    int mnm=INF;
    for(int i=0;i<k;i++)
        mnm=min(mnm,query(st,mij+i)+query(mij+i,dr));
    return mnm;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>k>>n>>m>>q;
    int a,b,c;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        con[b].push_back({a,c});
    }
    for(int i=0;i<n;i++)
    {
        ///calc dist[i][]
        dist[i][0]=0;
        for(int j=1;j<=min(i,dim-1);j++)
        {
            dist[i][j] = INF;
            for(auto adj:con[i])
                if(adj.first >= i-j)
                    dist[i][j]=min(dist[i][j], dist[adj.first][(adj.first - i + j)] + adj.second);
        }
    }
    int rez;
    for(int i=0;i<q;i++)
    {
        cin>>a>>b;
        rez=query(a,b);
        if(rez>=INF)
            rez=-1;
        cout<<rez<<"\n";
    }
    return 0;
}
/**



*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 392720 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7352 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 413 ms 392560 KB Output is correct
9 Correct 406 ms 392492 KB Output is correct
10 Correct 200 ms 390984 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 631 ms 392576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 5 ms 7376 KB Output is correct
7 Correct 7 ms 7380 KB Output is correct
8 Correct 9 ms 7484 KB Output is correct
9 Correct 8 ms 7380 KB Output is correct
10 Correct 418 ms 392412 KB Output is correct
11 Incorrect 685 ms 392504 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 5 ms 7376 KB Output is correct
7 Correct 7 ms 7380 KB Output is correct
8 Correct 9 ms 7484 KB Output is correct
9 Correct 8 ms 7380 KB Output is correct
10 Correct 418 ms 392412 KB Output is correct
11 Incorrect 685 ms 392504 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 392720 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 5 ms 7352 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 413 ms 392560 KB Output is correct
9 Correct 406 ms 392492 KB Output is correct
10 Correct 200 ms 390984 KB Output is correct
11 Incorrect 631 ms 392576 KB Output isn't correct
12 Halted 0 ms 0 KB -