제출 #292036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292036		Diuven	급행열차 20/19 (ROI19_express)	C++17	15 / 100	3142 ms	539616 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;
const int magic = 5000;

int n, m, q;
long long p;

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

void prune(int v) {
    int step = 0;
    if (len[v] <= magic) {
        return;
    }
    step = (len[v] + magic - 1) / magic;
    
    int ptr = 0;
    for (int i = 0; i < len[v]; i += step)
        help[ptr++] = dists[v][i];
    if (help[ptr - 1] != dists[v][len[v] - 1]) {
        help[ptr++] = dists[v][len[v] - 1];
    }
    for (int i = 0; i < ptr; i++)
        dists[v][i] = help[i];
    len[v] = ptr;
}

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];
            prune(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;
}

컴파일 시 표준 에러 (stderr) 메시지

main.cpp: In function 'int main()':
main.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%d", &tc);
      |     ~~~~~^~~~~~~~~~~
main.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |         scanf("%d%d%d%lld", &n, &m, &q, &p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |             scanf("%d%d%lld", &u, &v, &t);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |             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