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

Submission #6626721

Source codeソースコード

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

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

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

Submission

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

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:40: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:43:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int ai, bi; scanf("%d%d", &ai, &bi);
^

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 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 45 ms 1664 KB
scrambled_03.txt AC 40 ms 1536 KB
scrambled_04.txt AC 52 ms 1664 KB
scrambled_05.txt AC 59 ms 1152 KB
scrambled_06.txt AC 62 ms 1280 KB
scrambled_07.txt AC 20 ms 512 KB
scrambled_08.txt AC 23 ms 768 KB
scrambled_09.txt AC 42 ms 1664 KB
scrambled_10.txt AC 36 ms 1408 KB
scrambled_11.txt AC 12 ms 640 KB
scrambled_12.txt AC 35 ms 1408 KB
scrambled_13.txt AC 9 ms 512 KB
scrambled_14.txt TLE
scrambled_15.txt AC 623 ms 1664 KB
scrambled_16.txt TLE
scrambled_17.txt TLE
scrambled_18.txt TLE
scrambled_19.txt TLE
scrambled_20.txt TLE
scrambled_21.txt TLE
scrambled_22.txt TLE
scrambled_23.txt TLE
scrambled_24.txt TLE