oj.uz

Submission #420399

# Submission time Handle Problem Language Result Execution time Memory
420399 2021-06-08T10:42:45 Z ACmachine Airline Route Map (JOI18_airline) C++17
37 / 100
 678 ms 30472 KB 
#include <bits/stdc++.h>
#include "Alicelib.h"
#include <cassert>
#include <cstdio>
using namespace std;
#define pb push_back
#define FOR(i, j, k, l) for(int i = (j); i < (k); i+=(l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)


void Alice( int N, int M, int A[], int B[] ){ 
    vector<array<int, 2>> edges;
    REP(i, M){
        edges.pb({A[i], B[i]});
    }
    int curr = N;
    REP(i, 10){
        REP(j, N){
            if((j & (1 << i))){ // degrees of indicators will be non_increasing;       
                edges.pb({curr + i, j});
            }
        }
        if(i > 0){
            edges.pb({curr + i - 1, curr + i});
        }
    }
    // when I add one to everything but 1 other vertex, it means that it will have the biggest degree and it creates a pointer to the vertex without added edge;
    // use instead of the deg >= 2 trick
    curr += 10;
    REP(i, N + 10){
        edges.pb({curr, i});
    }
    curr++;
    REP(i, N){
        edges.pb({curr, i});
    }
    InitG(N + 12, (int)edges.size());
	REP(i, edges.size()){
        MakeG(i, edges[i][0], edges[i][1]);
    }
}

#include <bits/stdc++.h>
#include "Boblib.h"
#include <cassert>
#include <cstdio>
using namespace std;
#define pb push_back
#define FOR(i, j, k, l) for(int i = (j); i < (k); i+=(l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
void Bob( int V, int U, int C[], int D[] ){
    vector<array<int, 2>> edges;
    vector<vector<int>> g(V);
    vector<int> deg(V, 0);
    vector<vector<int>> mat(V, vector<int>(V, 0));
    REP(i, U){
        deg[C[i]]++;
        deg[D[i]]++;
        g[C[i]].pb(D[i]);
        g[D[i]].pb(C[i]);
        mat[C[i]][D[i]] = mat[D[i]][C[i]] = 1;
    }
    int f = -1, s = -1;
    REP(i, V){
        if(deg[i] == V - 2)
            f = i;
    }
    REP(i, V){
        if(i == f) continue;
        if(mat[f][i] == 0) 
            s = i;
    }
    vector<bool> ograph(V, false);
    vector<bool> indicator(V, true);
    for(int x : g[s])
        ograph[x] = true;
    ograph[f] = ograph[s] = false;
    for(int x : g[s])
        indicator[x] = false;
    indicator[f] = indicator[s] = false;
    vector<int> indicators;
    REP(i, V){
        if(indicator[i])
            indicators.pb(i);
    } 
    
    int start = indicators[0];
    vector<int> new_indicators; // in a chain order
    int pv = -1;
    int nstart = -1;
    REP(i, 9){
        nstart = -1;
        for(int x : g[start]){
            if(indicator[x] && x != pv){
                nstart = x;
                break;
            }
        }
        if(nstart != -1){
            pv = start;
            start = nstart; 
        }
        else
            break;
    }
    pv = -1;
    REP(i, 9){
        nstart = -1;
        new_indicators.pb(start);
        for(int x : g[start]){
            if(indicator[x] && x != pv){
                nstart = x;
                break;
            }
        }
        pv = start; 
        start = nstart; 
    }
    new_indicators.pb(start);
    indicators.swap(new_indicators);
    if(deg[indicators[0]] < deg[indicators.back()]){
        reverse(indicators.begin(), indicators.end()); 
    }  
    vector<int> mark(V, 0);
    REP(i, 10){
        int v = indicators[i];
        for(int x : g[v]){
            mark[x] |= (1 << i);
        }
    }
    REP(i, U){
        if(ograph[C[i]] && ograph[D[i]]){
            edges.pb({mark[C[i]], mark[D[i]]});
        }
    }
    InitMap( V - 12, (int)edges.size() );
    REP(i, edges.size()){
        MakeMap(edges[i][0], edges[i][1]);
    }	
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:7:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i+=(l))
      |                                            ^
Alice.cpp:9:19: note: in expansion of macro 'FOR'
    9 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
Alice.cpp:40:2: note: in expansion of macro 'REP'
   40 |  REP(i, edges.size()){
      |  ^~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:7:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i+=(l))
      |                                            ^
Bob.cpp:9:19: note: in expansion of macro 'FOR'
    9 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
Bob.cpp:97:5: note: in expansion of macro 'REP'
   97 |     REP(i, edges.size()){
      |     ^~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4580 KB Output is correct
2 Correct 3 ms 4588 KB Output is correct
3 Correct 3 ms 4516 KB Output is correct
4 Correct 3 ms 4592 KB Output is correct
5 Correct 3 ms 4588 KB Output is correct
6 Correct 3 ms 4556 KB Output is correct
7 Correct 3 ms 4528 KB Output is correct
8 Correct 3 ms 4588 KB Output is correct
9 Correct 3 ms 4612 KB Output is correct
10 Correct 3 ms 4584 KB Output is correct
11 Correct 3 ms 4588 KB Output is correct
12 Correct 4 ms 4584 KB Output is correct
13 Correct 3 ms 4588 KB Output is correct
14 Correct 3 ms 4588 KB Output is correct
15 Correct 3 ms 4516 KB Output is correct
16 Correct 3 ms 4572 KB Output is correct
17 Correct 3 ms 4496 KB Output is correct
18 Correct 3 ms 4496 KB Output is correct
19 Correct 3 ms 4588 KB Output is correct
20 Correct 3 ms 4496 KB Output is correct
21 Correct 3 ms 4600 KB Output is correct
22 Correct 3 ms 4596 KB Output is correct
23 Correct 3 ms 4528 KB Output is correct
24 Correct 3 ms 4580 KB Output is correct
25 Correct 3 ms 4588 KB Output is correct
26 Correct 3 ms 4568 KB Output is correct
27 Correct 3 ms 4568 KB Output is correct
28 Correct 3 ms 4580 KB Output is correct
29 Correct 3 ms 4568 KB Output is correct
30 Correct 3 ms 4584 KB Output is correct
31 Correct 3 ms 4584 KB Output is correct
32 Correct 4 ms 4496 KB Output is correct
33 Correct 3 ms 4564 KB Output is correct
34 Correct 3 ms 4584 KB Output is correct
35 Correct 3 ms 4564 KB Output is correct
36 Correct 3 ms 4568 KB Output is correct
37 Correct 3 ms 4588 KB Output is correct
38 Correct 3 ms 4584 KB Output is correct
39 Correct 3 ms 4516 KB Output is correct
40 Correct 3 ms 4540 KB Output is correct
41 Correct 4 ms 4588 KB Output is correct
42 Correct 3 ms 4588 KB Output is correct
43 Correct 3 ms 4572 KB Output is correct
44 Correct 3 ms 4584 KB Output is correct
45 Correct 3 ms 4564 KB Output is correct
46 Correct 3 ms 4572 KB Output is correct
47 Correct 3 ms 4600 KB Output is correct
48 Correct 4 ms 4588 KB Output is correct
49 Correct 3 ms 4592 KB Output is correct
50 Correct 3 ms 4516 KB Output is correct
51 Correct 3 ms 4544 KB Output is correct
52 Correct 4 ms 4588 KB Output is correct
53 Correct 3 ms 4584 KB Output is correct
54 Correct 3 ms 4588 KB Output is correct
55 Correct 3 ms 4568 KB Output is correct
56 Correct 3 ms 4588 KB Output is correct
57 Correct 3 ms 4588 KB Output is correct
58 Correct 3 ms 4568 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4580 KB Output is correct
2 Correct 3 ms 4588 KB Output is correct
3 Correct 3 ms 4516 KB Output is correct
4 Correct 3 ms 4592 KB Output is correct
5 Correct 3 ms 4588 KB Output is correct
6 Correct 3 ms 4556 KB Output is correct
7 Correct 3 ms 4528 KB Output is correct
8 Correct 3 ms 4588 KB Output is correct
9 Correct 3 ms 4612 KB Output is correct
10 Correct 3 ms 4584 KB Output is correct
11 Correct 3 ms 4588 KB Output is correct
12 Correct 4 ms 4584 KB Output is correct
13 Correct 3 ms 4588 KB Output is correct
14 Correct 3 ms 4588 KB Output is correct
15 Correct 3 ms 4516 KB Output is correct
16 Correct 3 ms 4572 KB Output is correct
17 Correct 3 ms 4496 KB Output is correct
18 Correct 3 ms 4496 KB Output is correct
19 Correct 3 ms 4588 KB Output is correct
20 Correct 3 ms 4496 KB Output is correct
21 Correct 3 ms 4600 KB Output is correct
22 Correct 3 ms 4596 KB Output is correct
23 Correct 3 ms 4528 KB Output is correct
24 Correct 3 ms 4580 KB Output is correct
25 Correct 3 ms 4588 KB Output is correct
26 Correct 3 ms 4568 KB Output is correct
27 Correct 3 ms 4568 KB Output is correct
28 Correct 3 ms 4580 KB Output is correct
29 Correct 3 ms 4568 KB Output is correct
30 Correct 3 ms 4584 KB Output is correct
31 Correct 3 ms 4584 KB Output is correct
32 Correct 4 ms 4496 KB Output is correct
33 Correct 3 ms 4564 KB Output is correct
34 Correct 3 ms 4584 KB Output is correct
35 Correct 3 ms 4564 KB Output is correct
36 Correct 3 ms 4568 KB Output is correct
37 Correct 3 ms 4588 KB Output is correct
38 Correct 3 ms 4584 KB Output is correct
39 Correct 3 ms 4516 KB Output is correct
40 Correct 3 ms 4540 KB Output is correct
41 Correct 4 ms 4588 KB Output is correct
42 Correct 3 ms 4588 KB Output is correct
43 Correct 3 ms 4572 KB Output is correct
44 Correct 3 ms 4584 KB Output is correct
45 Correct 3 ms 4564 KB Output is correct
46 Correct 3 ms 4572 KB Output is correct
47 Correct 3 ms 4600 KB Output is correct
48 Correct 4 ms 4588 KB Output is correct
49 Correct 3 ms 4592 KB Output is correct
50 Correct 3 ms 4516 KB Output is correct
51 Correct 3 ms 4544 KB Output is correct
52 Correct 4 ms 4588 KB Output is correct
53 Correct 3 ms 4584 KB Output is correct
54 Correct 3 ms 4588 KB Output is correct
55 Correct 3 ms 4568 KB Output is correct
56 Correct 3 ms 4588 KB Output is correct
57 Correct 3 ms 4588 KB Output is correct
58 Correct 3 ms 4568 KB Output is correct
59 Correct 4 ms 4628 KB Output is correct
60 Correct 4 ms 4644 KB Output is correct
61 Correct 3 ms 4588 KB Output is correct
62 Correct 3 ms 4588 KB Output is correct
63 Correct 3 ms 4588 KB Output is correct
64 Correct 3 ms 4588 KB Output is correct
65 Correct 3 ms 4720 KB Output is correct
66 Correct 3 ms 4724 KB Output is correct
67 Correct 3 ms 4716 KB Output is correct
68 Correct 4 ms 4512 KB Output is correct
69 Correct 3 ms 4568 KB Output is correct
70 Correct 3 ms 4568 KB Output is correct
71 Correct 4 ms 4696 KB Output is correct
72 Correct 3 ms 4668 KB Output is correct
73 Correct 3 ms 4716 KB Output is correct
74 Correct 3 ms 4516 KB Output is correct
75 Correct 3 ms 4576 KB Output is correct
76 Correct 3 ms 4588 KB Output is correct
77 Correct 3 ms 4716 KB Output is correct
78 Correct 3 ms 4716 KB Output is correct
79 Correct 3 ms 4588 KB Output is correct
80 Correct 3 ms 4496 KB Output is correct
81 Correct 3 ms 4572 KB Output is correct
82 Correct 3 ms 4744 KB Output is correct
83 Correct 3 ms 4592 KB Output is correct
84 Correct 3 ms 4516 KB Output is correct
85 Correct 3 ms 4568 KB Output is correct
86 Correct 3 ms 4716 KB Output is correct
87 Correct 3 ms 4600 KB Output is correct
88 Correct 3 ms 4588 KB Output is correct
89 Correct 3 ms 4564 KB Output is correct
90 Correct 3 ms 4516 KB Output is correct
91 Correct 3 ms 4576 KB Output is correct
92 Correct 3 ms 4516 KB Output is correct
93 Correct 3 ms 4580 KB Output is correct
94 Correct 3 ms 4584 KB Output is correct
95 Correct 3 ms 4716 KB Output is correct
96 Correct 3 ms 4716 KB Output is correct
97 Correct 3 ms 4624 KB Output is correct
98 Correct 4 ms 4728 KB Output is correct
99 Correct 3 ms 4588 KB Output is correct
100 Correct 3 ms 4508 KB Output is correct
101 Correct 3 ms 4600 KB Output is correct
102 Correct 3 ms 4592 KB Output is correct
103 Correct 3 ms 4604 KB Output is correct
104 Correct 3 ms 4592 KB Output is correct
105 Correct 3 ms 4692 KB Output is correct
106 Correct 3 ms 4716 KB Output is correct
107 Correct 3 ms 4588 KB Output is correct
108 Correct 3 ms 4588 KB Output is correct
109 Correct 3 ms 4716 KB Output is correct
110 Correct 3 ms 4588 KB Output is correct
111 Correct 3 ms 4528 KB Output is correct
112 Correct 3 ms 4568 KB Output is correct
113 Correct 3 ms 4588 KB Output is correct
114 Correct 3 ms 4516 KB Output is correct
115 Correct 3 ms 4716 KB Output is correct
116 Correct 3 ms 4528 KB Output is correct
117 Correct 3 ms 4516 KB Output is correct
118 Correct 3 ms 4696 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 678 ms 30472 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -