AtCoder Regular Contest 025

Submission #1647558

Source codeソースコード

#include <bits/stdc++.h>

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

int N, M, R, T;
int dist[3000];
vector<P> G[3000];

template <class T>
using priority_queue_with_greater = std::priority_queue<T, std::vector<T>, std::greater<T>>;

priority_queue_with_greater<P> pq;

template <typename T, typename U, int n>
void dijkstra(T s, std::vector<std::tuple<T, U>> (&graph)[n], U (&dist)[n], priority_queue_with_greater<std::tuple<U, T> > &pq){
    std::fill(dist, dist+n, std::numeric_limits<U>::max() / 2);
    dist[s] = 0;
    pq.emplace(dist[s], s);

    while(!pq.empty()){
        T u;
        U d;
        std::tie(d, u) = pq.top();
        pq.pop();

        if(dist[u] < d){continue;}

        for(const auto& p : graph[u]){
            T v;
            U c;
            std::tie(v, c) = p;
            if(dist[v] > d + c){
                dist[v] = d + c;
                pq.emplace(dist[v], v);
            }
        }
    }
}


int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::cin >> N >> M >> R >> T;

    for(int i=0;i<M;++i){
        int a, b, c;
        std::cin >> a >> b >> c;

        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }
    
    ll res = 0ll;
    for(int i=1;i<=N;++i){
        dijkstra(i, G, dist, pq);

        sort(dist+1, dist+1+N);

        for(int j=2;j<=N;++j){
            double u = 1. * dist[j] * R / T;
            
            // if minimizing, lb satisfies lb > ub
            // if maximizing, lb satisfies lb < ub
            int64_t lb = 1, ub = N + 1;
            
            while(std::abs(ub - lb) > 1){
                int64_t mid = (lb + ub) / 2;

                if(u >= dist[mid]){
                    lb = mid;
                }else{
                    ub = mid;
                }
            }

            ll c = N - lb - (T > R ? 1 : 0);
            res += c;
        }
    }

    std::cout << res << std::endl;
}

Submission

Task問題 C - ウサギとカメ
User nameユーザ名 tottoripaper
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2284 Byte
File nameファイル名
Exec time実行時間 1344 ms
Memory usageメモリ使用量 512 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample-01.txt,subtask0_sample-02.txt
All 100 / 100 subtask0_sample-01.txt,subtask0_sample-02.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample-01.txt AC 1 ms 384 KB
subtask0_sample-02.txt AC 1 ms 384 KB
subtask1_01.txt AC 1 ms 384 KB
subtask1_02.txt AC 1 ms 384 KB
subtask1_03.txt AC 1 ms 384 KB
subtask1_04.txt AC 1 ms 384 KB
subtask1_05.txt AC 7 ms 384 KB
subtask1_06.txt AC 9 ms 384 KB
subtask1_07.txt AC 29 ms 512 KB
subtask1_08.txt AC 40 ms 384 KB
subtask1_09.txt AC 388 ms 384 KB
subtask1_10.txt AC 386 ms 384 KB
subtask1_11.txt AC 151 ms 384 KB
subtask1_12.txt AC 1249 ms 512 KB
subtask1_13.txt AC 1245 ms 512 KB
subtask1_14.txt AC 1319 ms 512 KB
subtask1_15.txt AC 889 ms 512 KB
subtask1_16.txt AC 1344 ms 512 KB