東京大学プログラミングコンテスト2014

Submission #6629760

Source codeソースコード

#include <iostream>
#include <map>
#include <vector>
using namespace std;
using i64 = int64_t;

class Trie {
  struct Node {
    i64 x, y;
    map<int, Node*> children;
    Node() : x(0LL), y(0LL) {}
    ~Node() { for(auto &kv : children) { delete kv.second; } }
    i64 insert(int a, i64 b) {
      if(a == 0) {
        x += b;
        return x + y;
      }
      Node **nxt = &(children[a % 10]);
      if(*nxt == nullptr) { *nxt = new Node; }
      y = max(y, (*nxt)->insert(a / 10, b));
      return x + y;
    }
  };
  Node *root;
 public:
  Trie() { root = new Node; }
  ~Trie() { delete root; }
  i64 insert(int a, i64 b) { return root->insert(a, b); }
};

int main(void) {
  int n; scanf("%d", &n);
  Trie tree;
  for(int i=0; i<n; ++i) {
    int ai; i64 bi; scanf("%d%ld", &ai, &bi);
    i64 res = tree.insert(ai, bi);
    printf("%ld\n", res);
  }
  return 0;
}

Submission

Task問題 E - 宝くじ
User nameユーザ名 asc
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 200
Source lengthソースコード長 912 Byte
File nameファイル名
Exec time実行時間 226 ms
Memory usageメモリ使用量 73088 KB

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:32:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int n; scanf("%d", &n);
^
./Main.cpp:35:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int ai; i64 bi; scanf("%d%ld", &ai, &bi);
^

Test case

Set

Set name Score得点 / Max score Cases
All 200 / 200 scrambled_00.txt,scrambled_01.txt,scrambled_02.txt,scrambled_03.txt,scrambled_04.txt,scrambled_05.txt,scrambled_06.txt,scrambled_07.txt,scrambled_08.txt,scrambled_09.txt,scrambled_10.txt,scrambled_11.txt,scrambled_12.txt,scrambled_13.txt,scrambled_14.txt,scrambled_15.txt,scrambled_16.txt,scrambled_17.txt,scrambled_18.txt,scrambled_19.txt,scrambled_20.txt,scrambled_21.txt,scrambled_22.txt,scrambled_23.txt,scrambled_24.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
scrambled_00.txt AC 1 ms 256 KB
scrambled_01.txt AC 1 ms 256 KB
scrambled_02.txt AC 43 ms 1664 KB
scrambled_03.txt AC 38 ms 1536 KB
scrambled_04.txt AC 43 ms 1664 KB
scrambled_05.txt AC 29 ms 1152 KB
scrambled_06.txt AC 34 ms 1280 KB
scrambled_07.txt AC 11 ms 512 KB
scrambled_08.txt AC 19 ms 768 KB
scrambled_09.txt AC 38 ms 1664 KB
scrambled_10.txt AC 33 ms 1408 KB
scrambled_11.txt AC 11 ms 640 KB
scrambled_12.txt AC 32 ms 1408 KB
scrambled_13.txt AC 8 ms 512 KB
scrambled_14.txt AC 112 ms 30976 KB
scrambled_15.txt AC 5 ms 1792 KB
scrambled_16.txt AC 107 ms 29952 KB
scrambled_17.txt AC 15 ms 5504 KB
scrambled_18.txt AC 100 ms 28672 KB
scrambled_19.txt AC 212 ms 73088 KB
scrambled_20.txt AC 226 ms 65408 KB
scrambled_21.txt AC 138 ms 43008 KB
scrambled_22.txt AC 137 ms 42752 KB
scrambled_23.txt AC 24 ms 10368 KB
scrambled_24.txt AC 52 ms 20480 KB