AtCoder Grand Contest 012

Submission #1588847

Source codeソースコード

//
//  main.cpp
//  backToProblemSolving
//
//  Created by Khaled Abdelfattah on 6/27/17.
//  Copyright © 2017 Khaled Abdelfattah. All rights reserved.
//

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;

typedef long long ll;
#define MAX 1000000000
#define BASE1 23
#define BASE2 31
#define MOD1 1000000007
#define MOD2 217645177
#define eps 1e-6

vector<pair<int, int>> adjList[100005];
int n, m, bestDist[100005];
bool visited[100005];
priority_queue< pair<int, int>, vector<pair<int, int> >, greater< pair<int, int> > > pq;
int colors[100005];
void Dijkstra (int source, int d, int c) {
    for (int i = 0; i < n; ++i)
        bestDist[i] = INT_MAX, visited[i] = 0;
    pq.push(make_pair(0, source));
    bestDist[source] = 0;
    while (!pq.empty()) {
        pair<int, int> top = pq.top();
        pq.pop();
        int dist = top.first, v = top.second, sz = (int) adjList[v].size();
        if (visited[v])
            continue;
        visited[v] = true;
        for (int i = 0; i < sz; ++i) {
            pair<int, int> current = adjList[v][i];
            int neigh = current.first, weight = current.second;
            if (!visited[neigh] && bestDist[neigh] > dist + weight) {
                bestDist[neigh] = dist + weight;
                pq.push(make_pair(bestDist[neigh], neigh));
            }
        }
    }
    for (int i = 0; i < n; i ++)
        if (bestDist[i] <= d)
            colors[i] = c;
}
int main() {
    cin >> n >> m;
    memset(colors, 0, n);
    for (int i = 0; i < m; i ++) {
        int u, v;
        cin >> u >> v;
        v--, u--;
        adjList[u].push_back(make_pair(v, 1));
        adjList[v].push_back(make_pair(u, 1));
    }
    int q;
    cin >> q;
    while (q --) {
        int s, d, c;
        cin >> s >> d >> c;
        Dijkstra(s - 1, d, c);
    }
    for (int i = 0; i < n; i ++)
        cout << colors[i] << endl;
    return 0;
}

Submission

Task問題 B - Splatter Painting
User nameユーザ名 khaledJFT74
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 TLE
Score得点 200
Source lengthソースコード長 1976 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt
Subtask1 200 / 200 00_example_01.txt,00_example_02.txt,10_01.txt,10_02.txt,10_03.txt,10_04.txt,10_05.txt,10_06.txt,10_07.txt,10_08.txt,10_09.txt,10_10.txt,10_11.txt,10_12.txt,10_13.txt,10_14.txt,10_15.txt,10_16.txt,10_17.txt
All 0 / 500 00_example_01.txt,00_example_02.txt,10_01.txt,10_02.txt,10_03.txt,10_04.txt,10_05.txt,10_06.txt,10_07.txt,10_08.txt,10_09.txt,10_10.txt,10_11.txt,10_12.txt,10_13.txt,10_14.txt,10_15.txt,10_16.txt,10_17.txt,20_01.txt,20_02.txt,20_03.txt,20_04.txt,20_05.txt,20_06.txt,20_07.txt,20_08.txt,20_09.txt,20_10.txt,20_11.txt,20_12.txt,20_13.txt,20_14.txt,20_15.txt,20_16.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 2 ms 2560 KB
00_example_02.txt AC 2 ms 2560 KB
10_01.txt AC 3 ms 2688 KB
10_02.txt AC 2 ms 2560 KB
10_03.txt AC 3 ms 2560 KB
10_04.txt AC 3 ms 2560 KB
10_05.txt AC 3 ms 2688 KB
10_06.txt AC 2 ms 2560 KB
10_07.txt AC 5 ms 2560 KB
10_08.txt AC 258 ms 2688 KB
10_09.txt AC 274 ms 2688 KB
10_10.txt AC 269 ms 2688 KB
10_11.txt AC 257 ms 2688 KB
10_12.txt AC 265 ms 2688 KB
10_13.txt AC 67 ms 2688 KB
10_14.txt AC 26 ms 2688 KB
10_15.txt AC 14 ms 2688 KB
10_16.txt AC 394 ms 2688 KB
10_17.txt AC 394 ms 2688 KB
20_01.txt TLE
20_02.txt TLE
20_03.txt TLE
20_04.txt AC 500 ms 3840 KB
20_05.txt AC 130 ms 2560 KB
20_06.txt AC 936 ms 3712 KB
20_07.txt AC 72 ms 2560 KB
20_08.txt TLE
20_09.txt AC 24 ms 2688 KB
20_10.txt AC 1282 ms 2560 KB
20_11.txt TLE
20_12.txt TLE
20_13.txt TLE
20_14.txt TLE
20_15.txt TLE
20_16.txt TLE