AtCoder Grand Contest 012

Submission #1588612

Source codeソースコード

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

vector < vector < int > > graph;
int n, m, q, state[100050], color[100050], vis[100050];

int id = 1;

struct query
{
    int v, d, c;
}A[100050];

//void dfs(int node, int c, int dep)
//{
//    if(!color[node])
//        color[node] = c;
//    vis[node] = id;
//
//    if(dep == 0)    return;
//
//    for(int i = 0;i < graph[node].size();++i)
//    {
//        int to = graph[node][i];
//        if(vis[to] != id)
//        {
//            dfs(to, c, dep - 1);
//        }
//    }
//}

void bfs(int node, int c, int dep)
{
    queue < pair < int, int > > q;
    q.push({node, dep});
    vis[node] = id;
    while(!q.empty())
    {
        int v = q.front().first;
        int depth = q.front().second;
        q.pop();

        if(!color[v])       color[v] = c;
        if(depth == 0)      continue;

        if(state[v] >= depth)     continue;

        state[v] = depth;

        for(int i = 0;i < graph[v].size();++i)
        {
            int to = graph[v][i];
            if(vis[to] != id)
            {
                vis[v] = id;
                q.push(make_pair(to, depth - 1));
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    graph.resize(n + 5);
    for(int i = 0;i < m;++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        --a;--b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    scanf("%d", &q);
    for(int i = 0;i < q;++i)
    {
        scanf("%d%d%d", &A[i].v, &A[i].d, &A[i].c);
        --A[i].v;
    }
    memset(state, 0xff, sizeof(state));
    for(int i = q - 1;i > -1;--i)
    {
        ++id;
//        if(state[A[i].v] >= A[i].d)     continue;

//        state[A[i].v] = A[i].d;
        bfs(A[i].v, A[i].c, A[i].d);
    }

    for(int i = 0;i < n;++i)
    {
        printf("%d\n", color[i]);
    }
    return 0;
}

Submission

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

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:71:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
./Main.cpp:76:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
^
./Main.cpp:82:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
./Main.cpp:85:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &A[i].v, &A[i].d, &A[i].c);
^

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 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 1 ms 640 KB
00_example_02.txt AC 1 ms 640 KB
10_01.txt AC 2 ms 640 KB
10_02.txt AC 1 ms 640 KB
10_03.txt AC 1 ms 640 KB
10_04.txt AC 1 ms 640 KB
10_05.txt AC 2 ms 640 KB
10_06.txt AC 1 ms 640 KB
10_07.txt AC 1 ms 768 KB
10_08.txt AC 3 ms 768 KB
10_09.txt AC 3 ms 768 KB
10_10.txt AC 3 ms 768 KB
10_11.txt AC 3 ms 768 KB
10_12.txt AC 3 ms 768 KB
10_13.txt AC 2 ms 768 KB
10_14.txt AC 2 ms 768 KB
10_15.txt AC 2 ms 768 KB
10_16.txt AC 3 ms 768 KB
10_17.txt AC 3 ms 768 KB
20_01.txt AC 116 ms 8192 KB
20_02.txt AC 116 ms 8192 KB
20_03.txt AC 116 ms 8064 KB
20_04.txt AC 16 ms 1792 KB
20_05.txt AC 4 ms 768 KB
20_06.txt AC 12 ms 3840 KB
20_07.txt AC 4 ms 768 KB
20_08.txt AC 40 ms 1664 KB
20_09.txt AC 4 ms 768 KB
20_10.txt AC 33 ms 1536 KB
20_11.txt AC 40 ms 1920 KB
20_12.txt AC 47 ms 6784 KB
20_13.txt AC 78 ms 7808 KB
20_14.txt AC 89 ms 7936 KB
20_15.txt AC 90 ms 8968 KB
20_16.txt AC 90 ms 8984 KB