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

Submission #6629357

Source codeソースコード

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

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

      for(int i=0; i<cnt; ++i, cur=cur->parent) {
        for(auto &kv : cur->children) {
          cur->y = max(cur->y, kv.second->x + kv.second->y);
        }
      }
      for(auto &kv : cur->children) {
        cur->y = max(cur->y, kv.second->x + kv.second->y);
      }

      return cur->x + cur->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ソースコード長 1397 Byte
File nameファイル名
Exec time実行時間 288 ms
Memory usageメモリ使用量 73088 KB

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:50: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:53: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 46 ms 1664 KB
scrambled_03.txt AC 41 ms 1536 KB
scrambled_04.txt AC 47 ms 1664 KB
scrambled_05.txt AC 33 ms 1152 KB
scrambled_06.txt AC 38 ms 1280 KB
scrambled_07.txt AC 13 ms 512 KB
scrambled_08.txt AC 20 ms 768 KB
scrambled_09.txt AC 41 ms 1664 KB
scrambled_10.txt AC 35 ms 1408 KB
scrambled_11.txt AC 12 ms 640 KB
scrambled_12.txt AC 34 ms 1408 KB
scrambled_13.txt AC 9 ms 512 KB
scrambled_14.txt AC 141 ms 30976 KB
scrambled_15.txt AC 6 ms 1792 KB
scrambled_16.txt AC 135 ms 29952 KB
scrambled_17.txt AC 18 ms 5504 KB
scrambled_18.txt AC 129 ms 28672 KB
scrambled_19.txt AC 261 ms 73088 KB
scrambled_20.txt AC 288 ms 65408 KB
scrambled_21.txt AC 175 ms 43008 KB
scrambled_22.txt AC 172 ms 42752 KB
scrambled_23.txt AC 28 ms 10368 KB
scrambled_24.txt AC 65 ms 20480 KB