Submission #414931

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
414931	2021-05-31 10:44:42	Pro_ktmr	Construction of Highway (JOI18_construction)	C++17	100 / 100	1327 ms	87432 KiB

construction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
template<class T> bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
constexpr int dy[4]={-1,0,1,0};
constexpr int dx[4]={0,-1,0,1};
template<typename T>
struct SegmentTree{
private:
    int n, N;
    vector<T> node;
    function<T(T, T)> F;
    T E;
public:
    void init(int _n, function<T(T, T)> f, T e){
        F = f;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

construction.cpp: In function 'int siz(int)':
construction.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i=0; i<chi[v].size(); i++) s[v] += siz(chi[v][i]);
      |                  ~^~~~~~~~~~~~~~
construction.cpp: In function 'void HLD(int, int)':
construction.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i=0; i<chi[v].size(); i++){
      |                  ~^~~~~~~~~~~~~~
construction.cpp:146:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for(int i=0; i<chi[v].size(); i++){
      |                  ~^~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:171:5: note: in expansion of macro 'rep'
  171 |     rep(i, N){
      |     ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:176:5: note: in expansion of macro 'rep'
  176 |     rep(i, N) C[i] = lower_bound(all(z), C[i]) - z.begin();
      |     ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:177:5: note: in expansion of macro 'rep'
  177 |     rep(i, N-1){
      |     ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:188:5: note: in expansion of macro 'rep'
  188 |     rep(i, N-1){
      |     ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:192:9: note: in expansion of macro 'rep'
  192 |         rep(j, v.size()){
      |         ^~~
construction.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
construction.cpp:192:9: note: in expansion of macro 'rep'
  192 |         rep(j, v.size()){
      |         ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
construction.cpp:207:9: note: in expansion of macro 'rep'
  207 |         rep(j, memo.size()) segtree.update(memo[j], 0);
      |         ^~~
construction.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
construction.cpp:207:9: note: in expansion of macro 'rep'
  207 |         rep(j, memo.size()) segtree.update(memo[j], 0);
      |         ^~~
construction.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
construction.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         scanf("%d", C+i);
      |         ~~~~~^~~~~~~~~~~
construction.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         scanf("%d%d", A+i, B+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84