Submission #1195285


Source Code Expand

#include <bits/stdc++.h>

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(ll i=0;i<(n);i++)

using namespace std;


struct Node{
    ll pos;
    ll cost;
    bool operator< (const Node &r) const{
        return cost > r.cost;
    }
};

ll NODE_MAX = pow(10, 5) + 5;
ll INF = NODE_MAX + 5;

vector<ll> dijkstra(ll src, vector<ll>* g){
    priority_queue<Node> que;
    que.push({src,0});
    vector<ll> res(NODE_MAX,INF);
    while(que.size()){
        Node n = que.top(); que.pop();
        if(res[n.pos] == INF)   res[n.pos] = n.cost;
        else                    continue;
        
        for(auto e : g[n.pos]){
            que.push({e, n.cost + 1});
        }
    }
    return res;
}

int main(){
    ll n, m;
    cin >> n >> m;
    vector<ll> g[n+5];
    rep(i, m){
        ll a, b;
        cin >> a >> b;
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1);
    }


    vector<vector<set<ll>>> memo(n, vector<set<ll>>(n, set<ll>()));
    rep(src, n){
        vector<ll> res = dijkstra(src, g);
        rep(to, n){
            ll cost = res[to];
            if(cost < INF){
                memo[src][cost].insert(to);
                memo[to][cost].insert(src);
            }
        }
    }

    vector<ll> color(n, 0);
    ll q;
    cin >> q;
    rep(i, q){
        ll v, d, c;
        cin >> v >> d >> c;
        v--;
        rep(cost, d+1){
            for(auto e : memo[v][cost]) color[e] = c;
        }
    }

    rep(i, n){
        cout << color[i] << endl;
    }


    return 0;
}

Submission Info

Submission Time
Task B - Splatter Painting
User npz35
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1621 Byte
Status RE
Exec Time 3488 ms
Memory 376304 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 500
Status
AC × 2
AC × 8
TLE × 9
MLE × 1
RE × 1
AC × 13
TLE × 14
MLE × 1
RE × 7
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 1024 KB
00_example_02.txt AC 2 ms 1024 KB
10_01.txt AC 27 ms 2416 KB
10_02.txt AC 7 ms 1792 KB
10_03.txt AC 5 ms 1280 KB
10_04.txt AC 7 ms 1664 KB
10_05.txt AC 27 ms 2416 KB
10_06.txt RE 266 ms 1024 KB
10_07.txt AC 153 ms 140160 KB
10_08.txt TLE 2120 ms 303600 KB
10_09.txt TLE 2122 ms 313456 KB
10_10.txt TLE 2122 ms 309488 KB
10_11.txt MLE 1992 ms 303472 KB
10_12.txt TLE 2122 ms 311664 KB
10_13.txt TLE 2123 ms 331504 KB
10_14.txt TLE 2123 ms 328304 KB
10_15.txt TLE 2122 ms 318704 KB
10_16.txt TLE 2126 ms 376304 KB
10_17.txt TLE 2126 ms 376304 KB
20_01.txt TLE 2292 ms -485564 KB
20_02.txt TLE 2603 ms -485276 KB
20_03.txt RE 1769 ms -485044 KB
20_04.txt TLE 2245 ms -1866012 KB
20_05.txt AC 113 ms 23792 KB
20_06.txt RE 1804 ms -485504 KB
20_07.txt AC 86 ms 25316 KB
20_08.txt AC 1559 ms 23824 KB
20_09.txt AC 78 ms 40048 KB
20_10.txt AC 178 ms 8560 KB
20_11.txt TLE 2107 ms 50264 KB
20_12.txt RE 1997 ms -485504 KB
20_13.txt TLE 3488 ms -485208 KB
20_14.txt RE 1789 ms -485028 KB
20_15.txt RE 1609 ms -485036 KB
20_16.txt RE 1596 ms -485340 KB