oj.uz

Submission #119098

# Submission time Handle Problem Language Result Execution time Memory
119098 2019-06-20T10:23:21 Z TAISA_ Airline Route Map (JOI18_airline) C++14
37 / 100
 729 ms 29756 KB 
#include <bits/stdc++.h>
#include "Alicelib.h"
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
void Alice(int N, int M, int A[], int B[]) {
    vector<P> v;
    int s = N + 9, t = N + 10;
    for(int i = 0; i < N; i++) {
        v.push_back(P(i, s));
        for(int j = 0; j < 9; j++) {
            if((i >> j) & 1) {
                v.push_back(P(i, N + j));
            }
        }
    }
    for(int i = 0; i < 9; i++) {
        v.push_back(P(N + i, s));
        v.push_back(P(N + i, t));
        if(i < 8) {
            v.push_back(P(N + i, N + i + 1));
        }
    }
    InitG(N + 11, M + v.size());
    for(int i = 0; i < M; i++) {
        MakeG(i, A[i], B[i]);
    }
    for(int i = 0; i < v.size(); i++) {
        MakeG(M + i, v[i].first, v[i].second);
    }
}
#include <bits/stdc++.h>
#include "Boblib.h"
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
void Bob(int V, int U, int C[], int D[]) {
    vector<vector<int>> v(V);
    for(int i = 0; i < U; i++) {
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
    }
    int s, t;
    for(int i = 0; i < V; i++) {
        if(v[i].size() == V - 2) {
            vector<int> vis(V);
            vis[i] = 1;
            for(auto& e : v[i]) {
                vis[e] = 1;
            }
            for(int j = 0; j < V; j++) {
                if(!vis[j] && v[j].size() == 9) {
                    t = j;
                    break;
                }
            }
            s = i;
            break;
        }
    }
    vector<int> to(V), ts, vs(V);
    for(auto& i : v[t]) {
        to[i] = 1;
    }
    int i1 = -1, i2;
    for(auto& i : v[t]) {
        int c = 0;
        for(auto& e : v[i]) {
            if(e == t) {
                continue;
            }
            if(to[e]) {
                c++;
            }
        }
        if(c == 1) {
            if(i1 == -1) {
                i1 = i;
            } else {
                i2 = i;
            }
        }
    }
    int st;
    if(v[i1].size() > v[i2].size()) {
        st = i1;
    } else {
        st = i2;
    }
    for(int i = 0; i < 9; i++) {
        ts.push_back(st);
        vs[st] = 1;
        if(i == 8) {
            break;
        }
        int tmp;
        for(auto& e : v[st]) {
            if(to[e] && !vs[e]) {
                tmp = e;
                break;
            }
        }
        st = tmp;
    }
    vector<int> num(V, -1);
    for(int i = 0; i < 9; i++) {
        for(auto& e : v[ts[i]]) {
            if(e == t || e == s || to[e]) {
                continue;
            }
            num[e] = max(0, num[e]);
            num[e] += (1 << i);
        }
    }
    for(int i = 0; i < V; i++) {
        if(i == s || i == t || to[i] || num[i] != -1) {
            continue;
        }
        num[i] = 0;
        break;
    }
    vector<P> es;
    for(int i = 0; i < V; i++) {
        if(num[i] == -1) {
            continue;
        }
        for(auto& e : v[i]) {
            if(e == s || to[e]) {
                continue;
            }
            if(num[i] < num[e]) {
                es.push_back(P(num[i], num[e]));
            }
        }
    }
    InitMap(V - 11, es.size());
    for(auto p : es) {
        MakeMap(p.first, p.second);
    }
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++) {
                    ~~^~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:15:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v[i].size() == V - 2) {
            ~~~~~~~~~~~~^~~~~~~~
Bob.cpp:86:24: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(i == s || i == t || to[i] || num[i] != -1) {
                      ~~^~~~
Bob.cpp:86:14: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(i == s || i == t || to[i] || num[i] != -1) {
            ~~^~~~
Bob.cpp:73:12: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
         st = tmp;
         ~~~^~~~~
Bob.cpp:55:27: warning: 'i2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(v[i1].size() > v[i2].size()) {
                           ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Correct 7 ms 6656 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 8 ms 6656 KB Output is correct
5 Correct 7 ms 6656 KB Output is correct
6 Correct 8 ms 6656 KB Output is correct
7 Correct 8 ms 6656 KB Output is correct
8 Correct 7 ms 6912 KB Output is correct
9 Correct 8 ms 6656 KB Output is correct
10 Correct 8 ms 6912 KB Output is correct
11 Correct 9 ms 6912 KB Output is correct
12 Correct 8 ms 6656 KB Output is correct
13 Correct 8 ms 6656 KB Output is correct
14 Correct 8 ms 6656 KB Output is correct
15 Correct 9 ms 6912 KB Output is correct
16 Correct 8 ms 6656 KB Output is correct
17 Correct 8 ms 6656 KB Output is correct
18 Correct 7 ms 6656 KB Output is correct
19 Correct 8 ms 6752 KB Output is correct
20 Correct 8 ms 6656 KB Output is correct
21 Correct 8 ms 6912 KB Output is correct
22 Correct 7 ms 6656 KB Output is correct
23 Correct 8 ms 6912 KB Output is correct
24 Correct 7 ms 6912 KB Output is correct
25 Correct 7 ms 6912 KB Output is correct
26 Correct 8 ms 6912 KB Output is correct
27 Correct 8 ms 6656 KB Output is correct
28 Correct 7 ms 6656 KB Output is correct
29 Correct 8 ms 6912 KB Output is correct
30 Correct 8 ms 6656 KB Output is correct
31 Correct 8 ms 6656 KB Output is correct
32 Correct 7 ms 6912 KB Output is correct
33 Correct 8 ms 6912 KB Output is correct
34 Correct 7 ms 6912 KB Output is correct
35 Correct 7 ms 6912 KB Output is correct
36 Correct 7 ms 6712 KB Output is correct
37 Correct 8 ms 6656 KB Output is correct
38 Correct 8 ms 6656 KB Output is correct
39 Correct 8 ms 6656 KB Output is correct
40 Correct 8 ms 6656 KB Output is correct
41 Correct 8 ms 6656 KB Output is correct
42 Correct 8 ms 6656 KB Output is correct
43 Correct 8 ms 6912 KB Output is correct
44 Correct 7 ms 6744 KB Output is correct
45 Correct 8 ms 6656 KB Output is correct
46 Correct 7 ms 6912 KB Output is correct
47 Correct 8 ms 6656 KB Output is correct
48 Correct 7 ms 6912 KB Output is correct
49 Correct 8 ms 6656 KB Output is correct
50 Correct 8 ms 6912 KB Output is correct
51 Correct 8 ms 6912 KB Output is correct
52 Correct 8 ms 6912 KB Output is correct
53 Correct 8 ms 6656 KB Output is correct
54 Correct 8 ms 6656 KB Output is correct
55 Correct 8 ms 6912 KB Output is correct
56 Correct 9 ms 6912 KB Output is correct
57 Correct 8 ms 6752 KB Output is correct
58 Correct 7 ms 6912 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Correct 7 ms 6656 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 8 ms 6656 KB Output is correct
5 Correct 7 ms 6656 KB Output is correct
6 Correct 8 ms 6656 KB Output is correct
7 Correct 8 ms 6656 KB Output is correct
8 Correct 7 ms 6912 KB Output is correct
9 Correct 8 ms 6656 KB Output is correct
10 Correct 8 ms 6912 KB Output is correct
11 Correct 9 ms 6912 KB Output is correct
12 Correct 8 ms 6656 KB Output is correct
13 Correct 8 ms 6656 KB Output is correct
14 Correct 8 ms 6656 KB Output is correct
15 Correct 9 ms 6912 KB Output is correct
16 Correct 8 ms 6656 KB Output is correct
17 Correct 8 ms 6656 KB Output is correct
18 Correct 7 ms 6656 KB Output is correct
19 Correct 8 ms 6752 KB Output is correct
20 Correct 8 ms 6656 KB Output is correct
21 Correct 8 ms 6912 KB Output is correct
22 Correct 7 ms 6656 KB Output is correct
23 Correct 8 ms 6912 KB Output is correct
24 Correct 7 ms 6912 KB Output is correct
25 Correct 7 ms 6912 KB Output is correct
26 Correct 8 ms 6912 KB Output is correct
27 Correct 8 ms 6656 KB Output is correct
28 Correct 7 ms 6656 KB Output is correct
29 Correct 8 ms 6912 KB Output is correct
30 Correct 8 ms 6656 KB Output is correct
31 Correct 8 ms 6656 KB Output is correct
32 Correct 7 ms 6912 KB Output is correct
33 Correct 8 ms 6912 KB Output is correct
34 Correct 7 ms 6912 KB Output is correct
35 Correct 7 ms 6912 KB Output is correct
36 Correct 7 ms 6712 KB Output is correct
37 Correct 8 ms 6656 KB Output is correct
38 Correct 8 ms 6656 KB Output is correct
39 Correct 8 ms 6656 KB Output is correct
40 Correct 8 ms 6656 KB Output is correct
41 Correct 8 ms 6656 KB Output is correct
42 Correct 8 ms 6656 KB Output is correct
43 Correct 8 ms 6912 KB Output is correct
44 Correct 7 ms 6744 KB Output is correct
45 Correct 8 ms 6656 KB Output is correct
46 Correct 7 ms 6912 KB Output is correct
47 Correct 8 ms 6656 KB Output is correct
48 Correct 7 ms 6912 KB Output is correct
49 Correct 8 ms 6656 KB Output is correct
50 Correct 8 ms 6912 KB Output is correct
51 Correct 8 ms 6912 KB Output is correct
52 Correct 8 ms 6912 KB Output is correct
53 Correct 8 ms 6656 KB Output is correct
54 Correct 8 ms 6656 KB Output is correct
55 Correct 8 ms 6912 KB Output is correct
56 Correct 9 ms 6912 KB Output is correct
57 Correct 8 ms 6752 KB Output is correct
58 Correct 7 ms 6912 KB Output is correct
59 Correct 8 ms 6656 KB Output is correct
60 Correct 8 ms 6656 KB Output is correct
61 Correct 8 ms 6912 KB Output is correct
62 Correct 9 ms 6656 KB Output is correct
63 Correct 8 ms 6912 KB Output is correct
64 Correct 8 ms 6912 KB Output is correct
65 Correct 8 ms 6912 KB Output is correct
66 Correct 8 ms 6912 KB Output is correct
67 Correct 8 ms 6656 KB Output is correct
68 Correct 8 ms 6656 KB Output is correct
69 Correct 7 ms 6912 KB Output is correct
70 Correct 8 ms 6912 KB Output is correct
71 Correct 8 ms 6712 KB Output is correct
72 Correct 8 ms 6912 KB Output is correct
73 Correct 9 ms 6656 KB Output is correct
74 Correct 8 ms 6656 KB Output is correct
75 Correct 7 ms 6656 KB Output is correct
76 Correct 8 ms 6656 KB Output is correct
77 Correct 8 ms 6912 KB Output is correct
78 Correct 8 ms 6656 KB Output is correct
79 Correct 8 ms 6656 KB Output is correct
80 Correct 7 ms 6656 KB Output is correct
81 Correct 8 ms 6912 KB Output is correct
82 Correct 7 ms 6912 KB Output is correct
83 Correct 8 ms 6656 KB Output is correct
84 Correct 8 ms 6912 KB Output is correct
85 Correct 8 ms 6656 KB Output is correct
86 Correct 9 ms 6656 KB Output is correct
87 Correct 7 ms 6912 KB Output is correct
88 Correct 8 ms 6912 KB Output is correct
89 Correct 8 ms 6656 KB Output is correct
90 Correct 8 ms 6912 KB Output is correct
91 Correct 8 ms 6912 KB Output is correct
92 Correct 7 ms 6656 KB Output is correct
93 Correct 7 ms 6656 KB Output is correct
94 Correct 9 ms 6912 KB Output is correct
95 Correct 8 ms 6912 KB Output is correct
96 Correct 8 ms 6656 KB Output is correct
97 Correct 8 ms 6656 KB Output is correct
98 Correct 8 ms 6912 KB Output is correct
99 Correct 8 ms 6912 KB Output is correct
100 Correct 8 ms 6912 KB Output is correct
101 Correct 8 ms 6656 KB Output is correct
102 Correct 8 ms 6656 KB Output is correct
103 Correct 7 ms 6656 KB Output is correct
104 Correct 8 ms 6912 KB Output is correct
105 Correct 8 ms 6912 KB Output is correct
106 Correct 8 ms 6656 KB Output is correct
107 Correct 7 ms 6912 KB Output is correct
108 Correct 8 ms 6912 KB Output is correct
109 Correct 8 ms 6656 KB Output is correct
110 Correct 8 ms 6656 KB Output is correct
111 Correct 8 ms 6656 KB Output is correct
112 Correct 8 ms 6912 KB Output is correct
113 Correct 8 ms 6912 KB Output is correct
114 Correct 15 ms 6656 KB Output is correct
115 Correct 9 ms 6912 KB Output is correct
116 Correct 8 ms 6656 KB Output is correct
117 Correct 9 ms 6912 KB Output is correct
118 Correct 8 ms 6912 KB Output is correct

Subtask #3
0 / 63.0

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