Submission #3676312


Source Code Expand

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

#define NDEBUG
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


void solve(int N, int M, vi& a, vi& b, int Q, vi& v, vi& d, vi& c){
    vi masks(11, 0);
    rep(d,11) {
        masks[d] = (1 << (d+1))-1;
    }

    vvi ne(N);
    rep(i,M) {
        int ai = a[i], bi = b[i];
        ne[ai].pb(bi);
        ne[bi].pb(ai);
    }

    vi visited(N, 0);
    vi colors(N, 0);

    queue<ii> q;
    for (int i=Q-1; i>=0; --i) {
        int v0 = v[i], d0 = d[i], c0 = c[i];

        if (visited[v0] & (1 << d0)) continue;

        if (visited[v0] == 0) colors[v0] = c0;
        visited[v0] |= masks[d0];

        if (d0 == 0) continue;
        --d0;

        for (int u: ne[v0]) {
            q.emplace( u, d0 );
        }
        while (!q.empty()) {
            int u=q.front().first, d=q.front().second;
            q.pop();

            if (visited[u] & (1 << d)) continue;
            if (visited[u] == 0) colors[u] = c0;
            visited[u] |= masks[d];
            if (d == 0) continue;
            --d;

            for (int v: ne[u]) {
                if (visited[v] & (1 << d)) continue;
                q.emplace( v, d );
            }

        }
    }

    rep(i,N) {
        printf("%d\n", colors[i]);
    }
}

int main() {
    int N, M; scanf("%d %d", &N, &M);
    vi a(M), b(M);
    rep(i,M){
        scanf("%d %d", &a[i], &b[i]);
        --a[i]; --b[i];
    }
    int Q; scanf("%d", &Q);
    vi v(Q),d(Q),c(Q);
    rep(i,Q){
        scanf("%d %d %d", &v[i], &d[i], &c[i]);
        --v[i];
    }
    solve(N,M,a,b, Q,v,d,c);
    return 0;
}

Submission Info

Submission Time
Task B - Splatter Painting
User naoya_t
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2716 Byte
Status
Exec Time 122 ms
Memory 9768 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int N, M; scanf("%d %d", &N, &M);
                                     ^
./Main.cpp:97:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i], &b[i]);
                                     ^
./Main.cpp:100:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int Q; scanf("%d", &Q);
                           ^
./Main.cpp:103:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &v[i], &d[i], &c[i]);
                                               ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 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 500 / 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
Case Name Status Exec Time Memory
00_example_01.txt 2 ms 256 KB
00_example_02.txt 1 ms 256 KB
10_01.txt 2 ms 256 KB
10_02.txt 2 ms 256 KB
10_03.txt 2 ms 256 KB
10_04.txt 2 ms 256 KB
10_05.txt 2 ms 256 KB
10_06.txt 2 ms 256 KB
10_07.txt 2 ms 256 KB
10_08.txt 3 ms 384 KB
10_09.txt 3 ms 384 KB
10_10.txt 3 ms 384 KB
10_11.txt 3 ms 384 KB
10_12.txt 3 ms 384 KB
10_13.txt 3 ms 384 KB
10_14.txt 3 ms 384 KB
10_15.txt 2 ms 384 KB
10_16.txt 3 ms 384 KB
10_17.txt 3 ms 384 KB
20_01.txt 122 ms 8576 KB
20_02.txt 120 ms 8576 KB
20_03.txt 116 ms 8576 KB
20_04.txt 20 ms 1664 KB
20_05.txt 3 ms 384 KB
20_06.txt 14 ms 3456 KB
20_07.txt 4 ms 384 KB
20_08.txt 23 ms 1280 KB
20_09.txt 4 ms 384 KB
20_10.txt 22 ms 1152 KB
20_11.txt 29 ms 1536 KB
20_12.txt 66 ms 7040 KB
20_13.txt 93 ms 8192 KB
20_14.txt 101 ms 8192 KB
20_15.txt 90 ms 9720 KB
20_16.txt 92 ms 9768 KB