제출 #258975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258975		Bruteforceman	Treatment Project (JOI20_treatment)	C++11	35 / 100	3063 ms	4088 KiB

treatment

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 2e5 + 10;
    const long long inf = 1e16;
    long long d[maxn];
    struct data {
      int t, l, r, c;
    } a[maxn];
    int n;
    int par[maxn];
     
    int leftAfter(int x, int t) {
      if(x == 1) return 1;
      return x + t;
    }
    int rightAfter(int x, int t) {
      if(x == n) return n;
      return x - t;
    }
     
    bool isEdge(data p, data q) {
      if(p.t <= q.t) {
        return (q.l <= p.r - abs(q.t - p.t));
      } else {
        return (q.l + abs(p.t - q.t) <= p.r);
      }
    }
     
    int main() {
      int m;
      scanf("%d %d", &n, &m);
      for(int i = 1; i <= m; i++) {
        scanf("%d %d %d %d", &a[i].t, &a[i].l, &a[i].r, &a[i].c);
        a[i].l -= 1;
      }
      priority_queue <pair <long long, int>, 
                      vector <pair <long long, int>>,
                      greater <pair <long long, int>>> Q;
      for(int i = 1; i <= m; i++) {
        if(a[i].l == 0) {
          d[i] = a[i].c;
          Q.emplace(d[i], i);
        } else {
          d[i] = inf;
        }
      }
      while(!Q.empty()) {
        int node = Q.top().second;
        long long dist = Q.top().first;
        Q.pop();
        if(dist != d[node]) continue;
        for(int i = 1; i <= m; i++) {
          if(isEdge(a[node], a[i]) && d[i] > d[node] + a[i].c) {
            d[i] = d[node] + a[i].c;
            par[i] += 1;
            assert(par[i] == 1);
            Q.emplace(d[i], i);
          }
        }
      }
      long long ans = inf;
      for(int i = 1; i <= m; i++) {
        if(a[i].r == n) ans = min(ans, d[i]);
      }
      if(ans == inf) ans = -1;
      printf("%lld\n", ans);
      return 0;
    }

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

treatment.cpp: In function 'int main()':
treatment.cpp:31:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &m);
       ~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &a[i].t, &a[i].l, &a[i].r, &a[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61