Submission #292033

#	Time	Username	Problem	Language	Result	Execution time	Memory
292033		Diuven	Express 20/19 (ROI19_express)	C++17	15 / 100	7138 ms	1048580 KiB

express

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define sc second

const int csize = 1000 * 1000;

int n, m, q;
long long p;

int tc;
long long* dists[csize];
int len[csize];
vector <pair <int, long long> > vertex[csize];

int main () {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    
    scanf("%d", &tc);

    for (int tnum = 0; tnum < tc; tnum++) {
        scanf("%d%d%d%lld", &n, &m, &q, &p);

        for (int i = 0; i < m; i++) {
            int u, v;
            long long t;
            scanf("%d%d%lld", &u, &v, &t);
            vertex[v - 1].pb(mp(u - 1, t));
        }

        len[0] = 1;
        dists[0] = new long long[1];
        dists[0][0] = 0ll;
        for (int i = 1; i < n; i++) {
            int total = 0;
            for (int j = 0; j < (int) vertex[i].size(); j++) {
                total += len[vertex[i][j].fs];
            }        
            dists[i] = new long long[total];
            int cur = 0;
            for (int j = 0; j < (int) vertex[i].size(); j++) {
                int tg = vertex[i][j].fs;
                int curlen = len[tg];
                long long toadd = vertex[i][j].sc;
                for (int h = 0; h < curlen; h++) {
                    dists[i][cur++] = dists[tg][h] + toadd;
                }                
            }
            len[i] = cur;
            sort(dists[i], dists[i] + len[i]);

            len[i] = unique(dists[i], dists[i] + len[i]) - dists[i];
        }

        for (int i = 0; i < q; i++) {
            int tg;
            long long tlen;
            scanf("%d%lld", &tg, &tlen);
            tg--;

            int it = lower_bound(dists[tg], dists[tg] + len[tg], tlen) - dists[tg];
            if (it < len[tg] && dists[tg][it] <= tlen * p / (p - 1)) {
                printf("1");
            } else {
                printf("0");
            }
        }

        for (int i = 0; i < n; i++) {
            delete [] dists[i];
            vertex[i].clear();
        }

        printf("\n");
    }

    return 0;
}

Compilation message (stderr)

main.cpp: In function 'int main()':
main.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d", &tc);
      |     ~~~~~^~~~~~~~~~~
main.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |         scanf("%d%d%d%lld", &n, &m, &q, &p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |             scanf("%d%d%lld", &u, &v, &t);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |             scanf("%d%lld", &tg, &tlen);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 24
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11