oj.uz

Submission #292773

# Submission time Handle Problem Language Result Execution time Memory
292773 2020-09-07T13:14:35 Z 반딧불(#5810) Express 20/19 (ROI19_express) C++17
0 / 100
 488 ms 64376 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t;
int n, m, q, p;
vector<pair<int, ll> > link[500002];
set<pair<ll, ll> > st[500002];
int qf[500002]; ll qr[500002];

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d %d %d", &n, &m, &q, &p);
        for(int i=1; i<=n; i++) link[i].clear();
        for(int i=1; i<=m; i++){
            int x, y; ll d;
            scanf("%d %d %lld", &x, &y, &d);
            link[x].push_back({y, d});
        }
        for(int i=1; i<=q; i++){
            scanf("%d %lld", &qf[i], &qr[i]);
        }
        ll diff = qr[1] / (p-1);

        for(int i=1; i<=n; i++) st[i].clear();
        st[1].insert({-diff, 0LL});
        for(int i=1; i<=n; i++){
//            printf("i %d: ", i);
//            for(auto v: st[i]) printf("%lld~%lld, ", v.first, v.second);
//            puts("");

            for(auto nxt: link[i]){
                for(auto v: st[i]){
                    if(v.first + nxt.second <= qr[1]){
                        auto tmp = make_pair(v.first + nxt.second, v.second + nxt.second);
                        auto it = st[nxt.first].lower_bound(tmp);
                        if(it != st[nxt.first].end() && it->first-1 <= tmp.second){
                            tmp.second = max(tmp.second, it->second);
                            st[nxt.first].erase(it);
                            it = st[nxt.first].lower_bound(tmp);
                        }
                        if(it != st[nxt.first].begin() && tmp.first-1 <= prev(it)->second){
                            tmp.first = min(tmp.first, prev(it)->first);
                            st[nxt.first].erase(prev(it));
                        }
                        st[nxt.first].insert(tmp);
                    }
                }
            }
        }

        for(int i=1; i<=q; i++){
            if(st[qf[i]].empty()) printf("0");
            else{
                auto tmp = *st[qf[i]].rbegin();
                if(tmp.first <= qr[1] && qr[1] <= tmp.second) printf("1");
                else printf("0");
            }
        }
        puts("");
    }
}

Compilation message

express.cpp: In function 'int main()':
express.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~
express.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |         scanf("%d %d %d %d", &n, &m, &q, &p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
express.cpp:20:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |             scanf("%d %d %lld", &x, &y, &d);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
express.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |             scanf("%d %lld", &qf[i], &qr[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35584 KB Output is correct
2 Correct 24 ms 35584 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Correct 25 ms 35584 KB Output is correct
5 Correct 24 ms 35584 KB Output is correct
6 Correct 24 ms 35584 KB Output is correct
7 Correct 24 ms 35584 KB Output is correct
8 Correct 24 ms 35584 KB Output is correct
9 Correct 28 ms 35576 KB Output is correct
10 Incorrect 27 ms 35640 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35712 KB Output is correct
2 Correct 488 ms 64376 KB Output is correct
3 Incorrect 367 ms 41344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35712 KB Output is correct
2 Correct 488 ms 64376 KB Output is correct
3 Incorrect 367 ms 41344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35576 KB Output is correct
2 Correct 24 ms 35584 KB Output is correct
3 Correct 25 ms 35592 KB Output is correct
4 Correct 25 ms 35576 KB Output is correct
5 Correct 29 ms 35712 KB Output is correct
6 Correct 25 ms 35576 KB Output is correct
7 Correct 26 ms 35584 KB Output is correct
8 Correct 28 ms 36864 KB Output is correct
9 Correct 27 ms 35712 KB Output is correct
10 Incorrect 25 ms 35584 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35576 KB Output is correct
2 Correct 24 ms 35584 KB Output is correct
3 Correct 25 ms 35592 KB Output is correct
4 Correct 25 ms 35576 KB Output is correct
5 Correct 29 ms 35712 KB Output is correct
6 Correct 25 ms 35576 KB Output is correct
7 Correct 26 ms 35584 KB Output is correct
8 Correct 28 ms 36864 KB Output is correct
9 Correct 27 ms 35712 KB Output is correct
10 Incorrect 25 ms 35584 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

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