Submission #523362

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
523362	2022-02-07 14:34:01	CPSC	Construction of Highway (JOI18_construction)	C++14	16 / 100	2086 ms	28928 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
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int >
using namespace std;
const int N = 1e5 + 5;
int lv[N],sz[N],par[N],tree[N],in[N],out[N],tin,sizeofchain[N];
map <int, int> shes;
vector <int> v[N],tocomp;
vector < pii > vec[N];
int bigchild[N],chain[N],n,a[N],b[N],c[N];
void update(int idx, int val) {
    for (int i = idx; i < N; i += i&(-i)) {
        tree[i] += val;
    }
}
int getans(int idx) {
    int pas = 0;
    for (int i = idx; i > 0; i-=i&(-i)) {
        pas += tree[i];
    }
    return pas;
}
void dfs(int a, int p) {
    sz[a] = 1;
    lv[a] = lv[p] + 1;
    par[a] = p;
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

construction.cpp: In function 'void dfs(int, int)':
construction.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
construction.cpp: In function 'void dfs1(int, int)':
construction.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
construction.cpp: In function 'void dfs_chain(int, int)':
construction.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
construction.cpp: In function 'int getans(int, int)':
construction.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int i = 0; i < vec[lst].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
construction.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int i = 0; i < vv.size(); i++) {
      |                         ~~^~~~~~~~~~~
construction.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 0; i < pas.size(); i++) {
      |                     ~~^~~~~~~~~~~~
construction.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < pas.size(); i++) update(pas[i].f, -pas[i].s);
      |                     ~~^~~~~~~~~~~~
construction.cpp: In function 'void toadd(int, int)':
construction.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int i = 0; i < vec[lst].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
construction.cpp:129:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int i = idx; i < vec[lst].size(); i++) {
      |                           ~~^~~~~~~~~~~~~~~~~
construction.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for (int i = 0; i < vv.size(); i++) {
      |                         ~~^~~~~~~~~~~
construction.cpp: At global scope:
construction.cpp:144:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  144 | main() {
      | ^~~~
construction.cpp: In function 'int main()':
construction.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i = 1; i < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~

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