Submission #1588847
Source Code Expand
// // 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 Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | khaledJFT74 |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 1976 Byte |
Status | TLE |
Exec Time | 2104 ms |
Memory | 10356 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 0 / 500 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
Subtask1 | 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 | 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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
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 | 2104 ms | 7168 KB |
20_02.txt | TLE | 2104 ms | 7168 KB |
20_03.txt | TLE | 2104 ms | 9216 KB |
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 | 2103 ms | 2816 KB |
20_09.txt | AC | 24 ms | 2688 KB |
20_10.txt | AC | 1282 ms | 2560 KB |
20_11.txt | TLE | 2103 ms | 2816 KB |
20_12.txt | TLE | 2104 ms | 6784 KB |
20_13.txt | TLE | 2104 ms | 6912 KB |
20_14.txt | TLE | 2104 ms | 6784 KB |
20_15.txt | TLE | 2104 ms | 8564 KB |
20_16.txt | TLE | 2104 ms | 10356 KB |