oj.uz

Submission #133461

# Submission time Handle Problem Language Result Execution time Memory
133461 2019-07-20T19:24:13 Z duality Airline Route Map (JOI18_airline) C++11
0 / 100
 1016 ms 31208 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#include "Alicelib.h"

static vpii edges;
void Alice(int N,int M,int *A,int *B) {
    int i,j;
    for (i = 0; i < M; i++) edges.pb(mp(A[i],B[i]));
    for (i = 0; i < N; i++) edges.pb(mp(N,i));
    for (i = 0; i < 10; i++) edges.pb(mp(N+i+1,N+11));
    for (i = 1; i < 10; i++) edges.pb(mp(N+i,N+i+1));
    edges.pb(mp(N+2,N+4));
    for (i = 0; i < N; i++) {
        for (j = 0; j < 10; j++) {
            if ((i+7) & (1 << j)) edges.pb(mp(i,N+j+1));
        }
    }
    InitG(N+12,edges.size());
    for (i = 0; i < edges.size(); i++) MakeG(i,edges[i].first,edges[i].second);
}

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#include "Boblib.h"

static vpii edges;
bitset<1012> adjMat[1012];
vi adjList[1012];
int c[1012],num[1012];
void Bob(int V,int U,int *C,int *D) {
    int i,j;
    int x,y;
    int N = V-12;
    for (i = 0; i < U; i++) adjMat[C[i]][D[i]] = adjMat[D[i]][C[i]] = 1;
    for (i = 0; i < V; i++) c[i] = adjMat[i].count();
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if ((c[i] == N) && (c[j] == 10)) {
                bitset<1012> bs = adjMat[i] | adjMat[j];
                bs[i] = bs[j] = 1;
                if (bs.count() == V) {
                    x = i,y = j;
                    break;
                }
            }
        }
        if (j < V) break;
    }
    vi v,v2;
    for (i = 0; i < V; i++) {
        if (adjMat[y][i]) v.pb(i);
    }
    for (i = 0; i < v.size(); i++) {
        for (j = 0; j < v.size(); j++) {
            if (adjMat[v[i]][v[j]]) adjList[v[i]].pb(v[j]);
        }
    }
    for (i = 0; i < v.size(); i++) {
        if ((adjList[v[i]].size() == 1) && (adjList[adjList[v[i]][0]].size() == 3)) break;
    }
    int u = v[i];
    fill(num,num+V,-1);
    num[u] = 0;
    for (i = 1; i < 10; i++) {
        if (i == 1) u = adjList[u][0];
        else if (i == 2) {
            if (adjList[adjList[u][0]].size() == 2) u = adjList[u][0];
            else if (adjList[adjList[u][1]].size() == 2) u = adjList[u][1];
            else u = adjList[u][2];
        }
        else {
            for (j = 0; j < adjList[u].size(); j++) {
                if (num[adjList[u][j]] == -1) {
                    u = adjList[u][j];
                    break;
                }
            }
        }
        num[u] = i;
    }
    for (i = 0; i < V; i++) {
        if (adjMat[x][i]) v2.pb(i);
    }
    for (i = 0; i < v2.size(); i++) {
        int n = 0;
        for (j = 0; j < v.size(); j++) {
            if (adjMat[v2[i]][v[j]]) n |= (1 << num[v[j]]);
        }
        num[v2[i]] = n-7;
    }
    for (i = 0; i < v2.size(); i++) {
        for (j = i+1; j < v2.size(); j++) {
            if (adjMat[v2[i]][v2[j]]) edges.pb(mp(num[v2[i]],num[v2[j]]));
        }
    }
    InitMap(N,edges.size());
    for (i = 0; i < edges.size(); i++) MakeMap(edges[i].first,edges[i].second);
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) MakeG(i,edges[i].first,edges[i].second);
                 ~~^~~~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:26:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (bs.count() == V) {
                     ~~~~~~~~~~~^~~~
Bob.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
Bob.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < v.size(); j++) {
                     ~~^~~~~~~~~~
Bob.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
Bob.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < adjList[u].size(); j++) {
                         ~~^~~~~~~~~~~~~~~~~~~
Bob.cpp:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < v2.size(); i++) {
                 ~~^~~~~~~~~~~
Bob.cpp:71:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < v.size(); j++) {
                     ~~^~~~~~~~~~
Bob.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < v2.size(); i++) {
                 ~~^~~~~~~~~~~
Bob.cpp:77:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = i+1; j < v2.size(); j++) {
                       ~~^~~~~~~~~~~
Bob.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < edges.size(); i++) MakeMap(edges[i].first,edges[i].second);
                 ~~^~~~~~~~~~~~~~
Bob.cpp:17:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x,y;
         ^
Bob.cpp:17:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x,y;
           ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6640 KB Output is correct
2 Correct 9 ms 6896 KB Output is correct
3 Incorrect 8 ms 6896 KB Wrong Answer [11]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6640 KB Output is correct
2 Correct 9 ms 6896 KB Output is correct
3 Incorrect 8 ms 6896 KB Wrong Answer [11]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 31088 KB Output is correct : V - N = 12
2 Correct 722 ms 25648 KB Output is correct : V - N = 12
3 Correct 303 ms 14208 KB Output is correct : V - N = 12
4 Correct 17 ms 7408 KB Output is correct : V - N = 12
5 Correct 184 ms 11504 KB Output is correct : V - N = 12
6 Correct 626 ms 22496 KB Output is correct : V - N = 12
7 Correct 939 ms 30496 KB Output is correct : V - N = 12
8 Correct 851 ms 28152 KB Output is correct : V - N = 12
9 Correct 443 ms 17624 KB Output is correct : V - N = 12
10 Correct 60 ms 8424 KB Output is correct : V - N = 12
11 Correct 97 ms 9200 KB Output is correct : V - N = 12
12 Correct 500 ms 19304 KB Output is correct : V - N = 12
13 Correct 934 ms 29440 KB Output is correct : V - N = 12
14 Correct 914 ms 30248 KB Output is correct : V - N = 12
15 Correct 548 ms 20920 KB Output is correct : V - N = 12
16 Correct 136 ms 10240 KB Output is correct : V - N = 12
17 Correct 33 ms 7888 KB Output is correct : V - N = 12
18 Correct 345 ms 15888 KB Output is correct : V - N = 12
19 Correct 794 ms 27024 KB Output is correct : V - N = 12
20 Correct 940 ms 30888 KB Output is correct : V - N = 12
21 Correct 262 ms 13392 KB Output is correct : V - N = 12
22 Correct 200 ms 12136 KB Output is correct : V - N = 12
23 Correct 87 ms 9240 KB Output is correct : V - N = 12
24 Correct 11 ms 6896 KB Output is correct : V - N = 12
25 Correct 53 ms 8224 KB Output is correct : V - N = 12
26 Correct 166 ms 11200 KB Output is correct : V - N = 12
27 Correct 262 ms 13288 KB Output is correct : V - N = 12
28 Correct 229 ms 12784 KB Output is correct : V - N = 12
29 Correct 120 ms 9936 KB Output is correct : V - N = 12
30 Correct 15 ms 7408 KB Output is correct : V - N = 12
31 Correct 15 ms 7152 KB Output is correct : V - N = 12
32 Correct 15 ms 7152 KB Output is correct : V - N = 12
33 Correct 15 ms 7152 KB Output is correct : V - N = 12
34 Correct 15 ms 7160 KB Output is correct : V - N = 12
35 Correct 15 ms 7152 KB Output is correct : V - N = 12
36 Correct 976 ms 31208 KB Output is correct : V - N = 12
37 Correct 941 ms 30840 KB Output is correct : V - N = 12
38 Correct 963 ms 30840 KB Output is correct : V - N = 12
39 Correct 978 ms 31096 KB Output is correct : V - N = 12
40 Correct 978 ms 30968 KB Output is correct : V - N = 12
41 Correct 181 ms 11288 KB Output is correct : V - N = 12
42 Correct 147 ms 10424 KB Output is correct : V - N = 12
43 Correct 161 ms 10792 KB Output is correct : V - N = 12
44 Correct 17 ms 7152 KB Output is correct : V - N = 12
45 Correct 101 ms 9416 KB Output is correct : V - N = 12
46 Correct 323 ms 14896 KB Output is correct : V - N = 12
47 Correct 174 ms 11480 KB Output is correct : V - N = 12
48 Correct 440 ms 17888 KB Output is correct : V - N = 12
49 Correct 87 ms 9080 KB Output is correct : V - N = 12
50 Correct 30 ms 8120 KB Output is correct : V - N = 12
51 Correct 755 ms 25616 KB Output is correct : V - N = 12
52 Correct 17 ms 7408 KB Output is correct : V - N = 12
53 Correct 646 ms 22416 KB Output is correct : V - N = 12
54 Correct 834 ms 27624 KB Output is correct : V - N = 12
55 Correct 60 ms 8424 KB Output is correct : V - N = 12
56 Correct 478 ms 19120 KB Output is correct : V - N = 12
57 Correct 878 ms 29664 KB Output is correct : V - N = 12
58 Correct 131 ms 10200 KB Output is correct : V - N = 12
59 Correct 359 ms 15704 KB Output is correct : V - N = 12
60 Correct 925 ms 30464 KB Output is correct : V - N = 12
61 Correct 10 ms 6896 KB Output is correct : V - N = 12
62 Correct 9 ms 6896 KB Output is correct : V - N = 12
63 Correct 9 ms 6896 KB Output is correct : V - N = 12
64 Correct 9 ms 6896 KB Output is correct : V - N = 12
65 Correct 9 ms 6896 KB Output is correct : V - N = 12
66 Correct 9 ms 6640 KB Output is correct : V - N = 12
67 Correct 9 ms 6640 KB Output is correct : V - N = 12
68 Correct 9 ms 6640 KB Output is correct : V - N = 12
69 Correct 9 ms 6640 KB Output is correct : V - N = 12
70 Correct 9 ms 6640 KB Output is correct : V - N = 12
71 Correct 9 ms 6896 KB Output is correct : V - N = 12
72 Correct 9 ms 6896 KB Output is correct : V - N = 12
73 Correct 9 ms 6640 KB Output is correct : V - N = 12
74 Correct 9 ms 6640 KB Output is correct : V - N = 12
75 Correct 9 ms 6640 KB Output is correct : V - N = 12
76 Correct 9 ms 6896 KB Output is correct : V - N = 12
77 Correct 8 ms 6640 KB Output is correct : V - N = 12
78 Correct 9 ms 6896 KB Output is correct : V - N = 12
79 Correct 9 ms 6640 KB Output is correct : V - N = 12
80 Correct 9 ms 6640 KB Output is correct : V - N = 12
81 Correct 9 ms 6640 KB Output is correct : V - N = 12
82 Correct 9 ms 6640 KB Output is correct : V - N = 12
83 Correct 9 ms 6896 KB Output is correct : V - N = 12
84 Correct 8 ms 6640 KB Output is correct : V - N = 12
85 Correct 9 ms 6896 KB Output is correct : V - N = 12
86 Correct 9 ms 6640 KB Output is correct : V - N = 12
87 Correct 9 ms 7152 KB Output is correct : V - N = 12
88 Correct 10 ms 6640 KB Output is correct : V - N = 12
89 Correct 8 ms 6896 KB Output is correct : V - N = 12
90 Correct 8 ms 6640 KB Output is correct : V - N = 12
91 Correct 9 ms 6896 KB Output is correct : V - N = 12
92 Correct 9 ms 6896 KB Output is correct : V - N = 12
93 Correct 8 ms 6640 KB Output is correct : V - N = 12
94 Correct 9 ms 6640 KB Output is correct : V - N = 12
95 Correct 8 ms 6640 KB Output is correct : V - N = 12
96 Correct 10 ms 6640 KB Output is correct : V - N = 12
97 Correct 9 ms 6640 KB Output is correct : V - N = 12
98 Correct 10 ms 6696 KB Output is correct : V - N = 12
99 Correct 9 ms 6896 KB Output is correct : V - N = 12
100 Correct 9 ms 6896 KB Output is correct : V - N = 12
101 Correct 9 ms 6640 KB Output is correct : V - N = 12
102 Correct 9 ms 6640 KB Output is correct : V - N = 12
103 Correct 9 ms 6648 KB Output is correct : V - N = 12
104 Correct 9 ms 6648 KB Output is correct : V - N = 12
105 Correct 9 ms 6896 KB Output is correct : V - N = 12
106 Correct 9 ms 6896 KB Output is correct : V - N = 12
107 Correct 9 ms 6896 KB Output is correct : V - N = 12
108 Correct 9 ms 6640 KB Output is correct : V - N = 12
109 Correct 9 ms 6640 KB Output is correct : V - N = 12
110 Correct 8 ms 6640 KB Output is correct : V - N = 12
111 Correct 9 ms 6896 KB Output is correct : V - N = 12
112 Correct 8 ms 6640 KB Output is correct : V - N = 12
113 Correct 10 ms 6648 KB Output is correct : V - N = 12
114 Correct 9 ms 6640 KB Output is correct : V - N = 12
115 Correct 8 ms 6640 KB Output is correct : V - N = 12
116 Correct 9 ms 6896 KB Output is correct : V - N = 12
117 Correct 9 ms 6640 KB Output is correct : V - N = 12
118 Correct 9 ms 6896 KB Output is correct : V - N = 12
119 Correct 9 ms 6936 KB Output is correct : V - N = 12
120 Correct 9 ms 6896 KB Output is correct : V - N = 12
121 Correct 9 ms 6896 KB Output is correct : V - N = 12
122 Correct 8 ms 6640 KB Output is correct : V - N = 12
123 Correct 9 ms 6640 KB Output is correct : V - N = 12
124 Runtime error 10 ms 6640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
125 Halted 0 ms 0 KB -