oj.uz

Submission #480927

# Submission time Handle Problem Language Result Execution time Memory
480927 2021-10-18T19:58:24 Z DJeniUp Toll (BOI17_toll) C++17
46 / 100
 3000 ms 8912 KB 
#pragma GCC Optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define INF 1000000000000007
#define MOD 1000000007
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

ll k,n,m,o,res[10007],t[50007][7];

vector<pairll>v[50007];

struct D{
    ll l,r,q;
}d[10007];

bool mcp(D d1, D d2){
    if(d1.r/k==d2.r/k)return d1.l<d2.l;
    return d1.r>d2.r;
}

int main() {
    

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cin>>k>>n>>m>>o;
    scanf("%lld %lld %lld %lld", &k, &n, &m, &o);
    for(int i=1;i<=m;i++){
        ll l,r,c;
        //cin>>l>>r>>c;
        scanf("%lld %lld %lld", &l, &r, &c);
        v[l].pb({r,c});
    }
    for(int i=1;i<=o;i++){
        //cin>>d[i].l>>d[i].r;
        scanf("%lld %lld", &d[i].l, &d[i].r);
        d[i].q=i;
    }
    sort(d+1,d+1+o,mcp);
    ll x=0;
    for(int i=1;i<=o;i++){
        if(d[i].r/k!=d[i-1].r/k || i==1){
            x=d[i].r-d[i].r%k;
            for(int j=0;j<k;j++){
                t[x][j]=t[x+1][j]=t[x+2][j]=t[x+3][j]=t[x+4][j]=INF;
            }
            t[x][0]=t[x+1][1]=t[x+2][2]=t[x+3][3]=t[x+4][4]=0;
            for(int j=x-1;j>=d[i].l;j--){
                for(int y=0;y<k;y++){
                    t[j][y]=INF;
                    for(auto it: v[j]){
                        t[j][y]=min(t[j][y],t[it.fr][y]+it.sc);
                    }
                }
            }
        }
        if(d[i].l>d[i].r || t[d[i].l][d[i].r%k]==INF)res[d[i].q]=-1;
        else res[d[i].q]=t[d[i].l][d[i].r%k];
    }
    for(int i=1;i<=o;i++){
        //cout<<res[i]<<endl;
        printf("%lld\n", res[i]);
    }

}

Compilation message

toll.cpp:1: warning: ignoring '#pragma GCC Optimize' [-Wunknown-pragmas]
    1 | #pragma GCC Optimize("O3")
      | 
toll.cpp: In function 'int main()':
toll.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%lld %lld %lld %lld", &k, &n, &m, &o);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%lld %lld %lld", &l, &r, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%lld %lld", &d[i].l, &d[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 6084 KB Output is correct
2 Correct 1 ms 1496 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 4 ms 1612 KB Output is correct
8 Correct 1006 ms 6160 KB Output is correct
9 Correct 1150 ms 6016 KB Output is correct
10 Correct 270 ms 4548 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1612 KB Output is correct
8 Correct 4 ms 1612 KB Output is correct
9 Correct 4 ms 1612 KB Output is correct
10 Correct 48 ms 5700 KB Output is correct
11 Correct 63 ms 6708 KB Output is correct
12 Correct 112 ms 8056 KB Output is correct
13 Correct 134 ms 8696 KB Output is correct
14 Correct 99 ms 7276 KB Output is correct
15 Correct 67 ms 5072 KB Output is correct
16 Correct 66 ms 5068 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1612 KB Output is correct
8 Correct 4 ms 1612 KB Output is correct
9 Correct 4 ms 1612 KB Output is correct
10 Correct 48 ms 5700 KB Output is correct
11 Correct 63 ms 6708 KB Output is correct
12 Correct 112 ms 8056 KB Output is correct
13 Correct 134 ms 8696 KB Output is correct
14 Correct 99 ms 7276 KB Output is correct
15 Correct 67 ms 5072 KB Output is correct
16 Correct 66 ms 5068 KB Output is correct
17 Correct 785 ms 6828 KB Output is correct
18 Correct 1 ms 1484 KB Output is correct
19 Correct 1 ms 1484 KB Output is correct
20 Correct 1 ms 1484 KB Output is correct
21 Correct 1 ms 1484 KB Output is correct
22 Correct 1 ms 1484 KB Output is correct
23 Correct 5 ms 1612 KB Output is correct
24 Correct 6 ms 1612 KB Output is correct
25 Correct 8 ms 1764 KB Output is correct
26 Correct 7 ms 1740 KB Output is correct
27 Correct 319 ms 5880 KB Output is correct
28 Correct 1496 ms 8232 KB Output is correct
29 Correct 1596 ms 8912 KB Output is correct
30 Correct 1356 ms 7464 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 6084 KB Output is correct
2 Correct 1 ms 1496 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 4 ms 1612 KB Output is correct
8 Correct 1006 ms 6160 KB Output is correct
9 Correct 1150 ms 6016 KB Output is correct
10 Correct 270 ms 4548 KB Output is correct
11 Execution timed out 3049 ms 7004 KB Time limit exceeded
12 Halted 0 ms 0 KB -