oj.uz

Submission #166309

# Submission time Handle Problem Language Result Execution time Memory
166309 2019-12-01T14:12:35 Z georgerapeanu Airline Route Map (JOI18_airline) C++11
37 / 100
 1024 ms 30664 KB 
#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#pragma once
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 1e3;
const int LGMAX = 10;

void Alice( int n, int m, int a[], int b[] ){
    vector<pair<int,int> > edges;
    for(int i = 0;i < m;i++){
        edges.push_back({a[i] + 1,b[i] + 1});
    }

    for(int h = 0;h < LGMAX;h++){
        for(int i = 1;i <= n;i++){
            if((i >> h) & 1){
                edges.push_back({i,n + 1 + h});
            }
        }
    }

    int lst = n + LGMAX;
    for(int i = n + 1;i <= n + LGMAX;i++){
        for(int j = i + 1;j <= lst;j++){
            edges.push_back({i,j});
        }
        lst--;
    }

    for(int i = n + 1;i <= n + LGMAX;i++){
        edges.push_back({n + LGMAX + 1,i});
    }

    edges.push_back({n + LGMAX + 2,n + LGMAX + 1});

    InitG(n + LGMAX + 2,edges.size());

    for(int i = 0;i < (int)edges.size();i++){
        MakeG(i,edges[i].first - 1,edges[i].second - 1);
    }
}


#include "Boblib.h"
#include <cassert>
#include <cstdio>
#pragma once
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 1e3;
const int LGMAX = 10;

static int gr[NMAX + LGMAX + 5];
static vector<int> graph[NMAX + LGMAX + 5];
int exp_gr[LGMAX + 2];
int tag[NMAX + LGMAX + 5];

void Bob( int n, int m, int a[], int b[] ){
	for(int i = 0;i < m;i++){
        gr[a[i] + 1]++;
        gr[b[i] + 1]++; 
        graph[a[i] + 1].push_back(b[i] + 1);
        graph[b[i] + 1].push_back(a[i] + 1);
    }

    for(int h = 0;h < LGMAX;h++){
        exp_gr[h]++;
        for(int i = 1;i <= n - LGMAX - 2;i++){
            if((i >> h) & 1){
                exp_gr[h]++;
            }
        }
    }

    int lst = LGMAX - 1;

    for(int h = 0;h < LGMAX;h++){
        for(int i = h;i <= lst;i++){
            exp_gr[h]++;
            exp_gr[i]++;
        }
        lst--;
    }
    
    sort(exp_gr,exp_gr + LGMAX);
    reverse(exp_gr,exp_gr + LGMAX);


    int master_node = -1;
    int control_node = -1;

    for(int i = 1;i <= n;i++){
        if(gr[i] == 1){
            int node = graph[i][0];
            if(gr[node] != LGMAX + 1){
                continue;
            }

            for(int i = 0;i < (int)graph[node].size();i++){
                if(graph[node][i] == node){
                    swap(graph[node][i],graph[node].back());
                    break;
                }
            }

            sort(graph[node].begin(),graph[node].begin() + LGMAX,[&](int a,int b){return gr[a] > gr[b];});
            
            for(int i = 0;i < LGMAX;i++){
                if(exp_gr[i] != gr[graph[node][i]]){
                    continue;
                }
            }
            control_node = i;
            master_node = node;
            break;
        }
    }

    assert(master_node != -1 && control_node != -1);

    for(int i = 0;i < (int)graph[master_node].size();i++){
        if(graph[master_node][i] == control_node){
            swap(graph[master_node][i],graph[master_node].back());
            break;
        }
    }

    sort(graph[master_node].begin(),graph[master_node].begin() + LGMAX,[&](int a,int b){return gr[a] > gr[b];});
            
    tag[master_node] = -1;
    tag[control_node] = -1;

    for(int i = 0;i < LGMAX;i++){
        tag[graph[master_node][i]] = -1;
    }

    for(int i = 0;i < LGMAX;i++){
        for(auto it:graph[graph[master_node][i]]){
            if(tag[it] != -1){
                tag[it] |= (1 << i);
            }
        }
    }

    vector<pair<int,int> > edges;

    for(int i = 0;i < m;i++){
        if(tag[a[i] + 1] != -1 && tag[b[i] + 1] != -1){
            edges.push_back({tag[a[i] + 1],tag[b[i] + 1]});
        }
    }

    InitMap(n - LGMAX - 2,edges.size());

    for(auto it:edges){
        MakeMap(it.first - 1,it.second - 1);
    }
}

Compilation message

Alice.cpp:4:9: warning: #pragma once in main file
 #pragma once
         ^~~~

Bob.cpp:4:9: warning: #pragma once in main file
 #pragma once
         ^~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1024 ms 30664 KB Output is correct : V - N = 12
2 Correct 785 ms 25708 KB Output is correct : V - N = 12
3 Correct 295 ms 14048 KB Output is correct : V - N = 12
4 Correct 16 ms 7416 KB Output is correct : V - N = 12
5 Correct 191 ms 11320 KB Output is correct : V - N = 12
6 Correct 652 ms 23784 KB Output is correct : V - N = 12
7 Correct 983 ms 30256 KB Output is correct : V - N = 12
8 Correct 872 ms 27768 KB Output is correct : V - N = 12
9 Correct 444 ms 17240 KB Output is correct : V - N = 12
10 Correct 59 ms 8168 KB Output is correct : V - N = 12
11 Correct 88 ms 9192 KB Output is correct : V - N = 12
12 Correct 522 ms 18984 KB Output is correct : V - N = 12
13 Correct 918 ms 29256 KB Output is correct : V - N = 12
14 Correct 993 ms 29752 KB Output is correct : V - N = 12
15 Correct 552 ms 22608 KB Output is correct : V - N = 12
16 Correct 132 ms 9976 KB Output is correct : V - N = 12
17 Correct 28 ms 7760 KB Output is correct : V - N = 12
18 Correct 281 ms 15712 KB Output is correct : V - N = 12
19 Correct 834 ms 26584 KB Output is correct : V - N = 12
20 Correct 952 ms 30464 KB Output is correct : V - N = 12
21 Correct 247 ms 13232 KB Output is correct : V - N = 12
22 Failed 210 ms 11792 KB Wrong Answer [13]
23 Halted 0 ms 0 KB -