oj.uz

Submission #482062

# Submission time Handle Problem Language Result Execution time Memory
482062 2021-10-22T21:36:50 Z leaked Airline Route Map (JOI18_airline) C++14
0 / 100
 742 ms 21080 KB 
#include "Alicelib.h"
#include <cassert>
#include <cstdio>
void Alice( int N, int M, int A[], int B[] );
void InitG( int V, int U );
void MakeG( int pos, int C, int D );
void Alice( int N, int M, int A[], int B[] ){
	int V=N+12,U=M;
	for(int i=0;i<N;i++){
        for(int j=0;j<10;j++){
            if(i&(1<<j))
                U++;
        }
        U++;
	}
	for(int j=0;j<9;j++) U++,U++;
	//U++;
    InitG(V,U);
    U=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<10;j++){
            if(i&(1<<j))
                MakeG(U++,i,N+j);
        }
        MakeG(U++,i,N+10);
	}
	for(int i=0;i<M;i++) MakeG(U++,A[i],B[i]);
	for(int j=0;j<9;j++)
        MakeG(U++,N+j,N+j+1);
    for(int j=1;j<10;j++) MakeG(U++,N+j,N+11);
}


#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

void Bob( int V, int U, int C[], int D[] ){
	int N=V-12;
	int M=U;
	for(int i=0;i<N;i++){
        for(int j=0;j<10;j++){
            if(i&(1<<j)) M--;
        }
        M--;
	}
//	debug()<<imie(N);
//	for(int i=0;i<M;i++) debug()<<imie(C[i])imie(D[i]);
	for(int j=0;j<9;j++) M--,M--;
    InitMap(N,M);
//    vec<bool> bad(V,1);
    vec<vec<int>>g(V,vec<int>());
    for(int i=0;i<U;i++)
        g[C[i]].pb(D[i]),g[D[i]].pb(C[i]);
    int cnt=0;
    vec<int>obr(V,0);
//    debug()<<imie(N);
    vec<bool>rbad;
    for(int i=0;i<V;i++){
//        deb
        if(sz(g[i])==N){
//            debug()<<imie(i)imie(g[i]);
            /// should be the main
            vec<bool> bad(V,1);
            for(auto &u : g[i]) bad[u]=0;
            bad[i]=0;
            vec<int>path;vec<int>they;
            vec<vec<int>>how(12,vec<int>());

            for(int v=0;v<V;v++){
                if(bad[v]){
                    they.pb(v);
                    for(auto &u : g[v]){
                        if(bad[u]) how[sz(they)-1].pb(u);
                    }
                }
            }
//            debug()<<imie(i)imie(sz(they));
            if(sz(they)!=11) continue;
            cnt++;///i'm sure that it's main
            vec<bool>start(11,1);
//            debug()<<imie(they);
            int kk=0;
            for(int i=0;i<sz(they);i++){
                int v=they[i];
//                debug()<<imie(g[v])imie(how[i]);
                sort(all(g[v]));sort(all(how[i]));
                if(how[i]==g[v] && sz(g[v])==9){
                    for(auto &u : g[v])
                        start[find(all(they),u)-they.begin()]=0;
                    for(auto &u : g[v]){
                        g[u].erase(find(all(g[u]),v),find(all(g[u]),v)+1);
                    }
                    start[i]=0;
                    kk=1;
//                    debug()<<imie(kk);
                    break;
                }
            }
            if(!kk) continue;
//            debug()<<imie(they)imie(start);
            for(int i=0;i<sz(they);i++){
                if(start[i]){
                    path.pb(they[i]);
                    for(int j=0;j<10;j++){
                        int v=path.back();
//                        debug()<<imie(v)imie(bad[15])imie(g[v]);
                        for(auto &u : g[v]){
                            if(bad[u] && (sz(path)==1 || path[sz(path)-2]!=u)){
                                path.pb(u);
                                break;
                            }
                        }
                    }
//                    debug()<<imie(path);
                }
            }
            for(int j=0;j<10;j++){
//                debug()<<imie(j)imie(path[j])imie(g[path[j]]);
                for(auto &u : g[path[j]]){
                    if(!bad[u]){
//                        debug()<<imie(path[j])imie(g[path[j]]);
                        obr[u]+=(1<<j);
                    }
                }
            }
            rbad=bad;
            rbad[i]=1;
            break;
        }
    }
//    debug()<<imie(obr);
    for(int i=0;i<U;i++){
        if(rbad[C[i]] || rbad[D[i]]) continue;
        MakeMap(obr[C[i]],obr[D[i]]);
    }
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4568 KB Output is correct
2 Correct 3 ms 4528 KB Output is correct
3 Correct 3 ms 4596 KB Output is correct
4 Correct 2 ms 4584 KB Output is correct
5 Correct 2 ms 4596 KB Output is correct
6 Correct 2 ms 4588 KB Output is correct
7 Correct 3 ms 4588 KB Output is correct
8 Correct 2 ms 4588 KB Output is correct
9 Correct 1 ms 4568 KB Output is correct
10 Correct 3 ms 4492 KB Output is correct
11 Correct 3 ms 4596 KB Output is correct
12 Correct 3 ms 4592 KB Output is correct
13 Correct 3 ms 4588 KB Output is correct
14 Incorrect 3 ms 4588 KB Wrong Answer [14]
15 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4568 KB Output is correct
2 Correct 3 ms 4528 KB Output is correct
3 Correct 3 ms 4596 KB Output is correct
4 Correct 2 ms 4584 KB Output is correct
5 Correct 2 ms 4596 KB Output is correct
6 Correct 2 ms 4588 KB Output is correct
7 Correct 3 ms 4588 KB Output is correct
8 Correct 2 ms 4588 KB Output is correct
9 Correct 1 ms 4568 KB Output is correct
10 Correct 3 ms 4492 KB Output is correct
11 Correct 3 ms 4596 KB Output is correct
12 Correct 3 ms 4592 KB Output is correct
13 Correct 3 ms 4588 KB Output is correct
14 Incorrect 3 ms 4588 KB Wrong Answer [14]
15 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 21080 KB Output is correct : V - N = 12
2 Correct 481 ms 18252 KB Output is correct : V - N = 12
3 Correct 226 ms 10400 KB Output is correct : V - N = 12
4 Correct 7 ms 4972 KB Output is correct : V - N = 12
5 Correct 98 ms 8152 KB Output is correct : V - N = 12
6 Correct 485 ms 16744 KB Output is correct : V - N = 12
7 Correct 711 ms 20800 KB Output is correct : V - N = 12
8 Correct 655 ms 19592 KB Output is correct : V - N = 12
9 Correct 328 ms 11984 KB Output is correct : V - N = 12
10 Correct 40 ms 5600 KB Output is correct : V - N = 12
11 Correct 72 ms 6440 KB Output is correct : V - N = 12
12 Correct 231 ms 13928 KB Output is correct : V - N = 12
13 Correct 413 ms 20184 KB Output is correct : V - N = 12
14 Correct 623 ms 20452 KB Output is correct : V - N = 12
15 Correct 295 ms 15956 KB Output is correct : V - N = 12
16 Correct 66 ms 7160 KB Output is correct : V - N = 12
17 Correct 15 ms 5484 KB Output is correct : V - N = 12
18 Correct 256 ms 11216 KB Output is correct : V - N = 12
19 Correct 496 ms 19032 KB Output is correct : V - N = 12
20 Correct 652 ms 20912 KB Output is correct : V - N = 12
21 Correct 205 ms 10012 KB Output is correct : V - N = 12
22 Correct 163 ms 8240 KB Output is correct : V - N = 12
23 Correct 41 ms 6176 KB Output is correct : V - N = 12
24 Correct 4 ms 4824 KB Output is correct : V - N = 12
25 Correct 32 ms 5668 KB Output is correct : V - N = 12
26 Correct 96 ms 7904 KB Output is correct : V - N = 12
27 Correct 180 ms 9000 KB Output is correct : V - N = 12
28 Correct 182 ms 8636 KB Output is correct : V - N = 12
29 Correct 78 ms 6692 KB Output is correct : V - N = 12
30 Correct 7 ms 5080 KB Output is correct : V - N = 12
31 Correct 7 ms 4780 KB Output is correct : V - N = 12
32 Correct 5 ms 4776 KB Output is correct : V - N = 12
33 Correct 6 ms 4896 KB Output is correct : V - N = 12
34 Correct 6 ms 4912 KB Output is correct : V - N = 12
35 Correct 7 ms 4840 KB Output is correct : V - N = 12
36 Correct 622 ms 21048 KB Output is correct : V - N = 12
37 Correct 533 ms 20932 KB Output is correct : V - N = 12
38 Correct 465 ms 21000 KB Output is correct : V - N = 12
39 Correct 742 ms 21032 KB Output is correct : V - N = 12
40 Correct 553 ms 21076 KB Output is correct : V - N = 12
41 Correct 125 ms 7912 KB Output is correct : V - N = 12
42 Correct 76 ms 7360 KB Output is correct : V - N = 12
43 Correct 118 ms 7840 KB Output is correct : V - N = 12
44 Correct 8 ms 4952 KB Output is correct : V - N = 12
45 Correct 70 ms 6492 KB Output is correct : V - N = 12
46 Correct 152 ms 10776 KB Output is correct : V - N = 12
47 Correct 99 ms 7916 KB Output is correct : V - N = 12
48 Correct 328 ms 12196 KB Output is correct : V - N = 12
49 Correct 33 ms 6288 KB Output is correct : V - N = 12
50 Correct 19 ms 5408 KB Output is correct : V - N = 12
51 Correct 538 ms 18272 KB Output is correct : V - N = 12
52 Correct 7 ms 4852 KB Output is correct : V - N = 12
53 Correct 331 ms 16680 KB Output is correct : V - N = 12
54 Correct 385 ms 19208 KB Output is correct : V - N = 12
55 Correct 27 ms 5684 KB Output is correct : V - N = 12
56 Correct 365 ms 13548 KB Output is correct : V - N = 12
57 Correct 660 ms 20196 KB Output is correct : V - N = 12
58 Correct 83 ms 7120 KB Output is correct : V - N = 12
59 Correct 219 ms 11168 KB Output is correct : V - N = 12
60 Correct 546 ms 20540 KB Output is correct : V - N = 12
61 Correct 3 ms 4588 KB Output is correct : V - N = 12
62 Correct 2 ms 4588 KB Output is correct : V - N = 12
63 Correct 2 ms 4588 KB Output is correct : V - N = 12
64 Correct 3 ms 4588 KB Output is correct : V - N = 12
65 Correct 3 ms 4588 KB Output is correct : V - N = 12
66 Correct 3 ms 4588 KB Output is correct : V - N = 12
67 Correct 3 ms 4532 KB Output is correct : V - N = 12
68 Correct 3 ms 4572 KB Output is correct : V - N = 12
69 Correct 3 ms 4588 KB Output is correct : V - N = 12
70 Correct 3 ms 4588 KB Output is correct : V - N = 12
71 Correct 2 ms 4588 KB Output is correct : V - N = 12
72 Correct 3 ms 4596 KB Output is correct : V - N = 12
73 Correct 3 ms 4588 KB Output is correct : V - N = 12
74 Correct 3 ms 4588 KB Output is correct : V - N = 12
75 Correct 2 ms 4588 KB Output is correct : V - N = 12
76 Correct 3 ms 4588 KB Output is correct : V - N = 12
77 Correct 3 ms 4588 KB Output is correct : V - N = 12
78 Correct 3 ms 4588 KB Output is correct : V - N = 12
79 Correct 3 ms 4600 KB Output is correct : V - N = 12
80 Correct 3 ms 4716 KB Output is correct : V - N = 12
81 Correct 3 ms 4588 KB Output is correct : V - N = 12
82 Correct 2 ms 4584 KB Output is correct : V - N = 12
83 Correct 3 ms 4588 KB Output is correct : V - N = 12
84 Correct 1 ms 4596 KB Output is correct : V - N = 12
85 Correct 3 ms 4588 KB Output is correct : V - N = 12
86 Correct 2 ms 4592 KB Output is correct : V - N = 12
87 Correct 3 ms 4588 KB Output is correct : V - N = 12
88 Correct 2 ms 4588 KB Output is correct : V - N = 12
89 Correct 5 ms 4496 KB Output is correct : V - N = 12
90 Correct 3 ms 4584 KB Output is correct : V - N = 12
91 Correct 2 ms 4576 KB Output is correct : V - N = 12
92 Correct 2 ms 4584 KB Output is correct : V - N = 12
93 Correct 2 ms 4656 KB Output is correct : V - N = 12
94 Correct 3 ms 4516 KB Output is correct : V - N = 12
95 Correct 3 ms 4584 KB Output is correct : V - N = 12
96 Correct 3 ms 4588 KB Output is correct : V - N = 12
97 Correct 3 ms 4588 KB Output is correct : V - N = 12
98 Correct 3 ms 4536 KB Output is correct : V - N = 12
99 Correct 3 ms 4596 KB Output is correct : V - N = 12
100 Correct 3 ms 4540 KB Output is correct : V - N = 12
101 Correct 3 ms 4588 KB Output is correct : V - N = 12
102 Correct 2 ms 4592 KB Output is correct : V - N = 12
103 Correct 2 ms 4516 KB Output is correct : V - N = 12
104 Correct 3 ms 4592 KB Output is correct : V - N = 12
105 Correct 2 ms 4588 KB Output is correct : V - N = 12
106 Correct 3 ms 4584 KB Output is correct : V - N = 12
107 Correct 3 ms 4588 KB Output is correct : V - N = 12
108 Correct 3 ms 4588 KB Output is correct : V - N = 12
109 Correct 3 ms 4572 KB Output is correct : V - N = 12
110 Correct 3 ms 4588 KB Output is correct : V - N = 12
111 Correct 3 ms 4588 KB Output is correct : V - N = 12
112 Correct 2 ms 4588 KB Output is correct : V - N = 12
113 Correct 3 ms 4588 KB Output is correct : V - N = 12
114 Correct 3 ms 4588 KB Output is correct : V - N = 12
115 Correct 3 ms 4588 KB Output is correct : V - N = 12
116 Correct 2 ms 4588 KB Output is correct : V - N = 12
117 Correct 2 ms 4588 KB Output is correct : V - N = 12
118 Correct 1 ms 4588 KB Output is correct : V - N = 12
119 Correct 3 ms 4588 KB Output is correct : V - N = 12
120 Correct 2 ms 4588 KB Output is correct : V - N = 12
121 Correct 3 ms 4588 KB Output is correct : V - N = 12
122 Correct 1 ms 4588 KB Output is correct : V - N = 12
123 Correct 3 ms 4596 KB Output is correct : V - N = 12
124 Correct 3 ms 4584 KB Output is correct : V - N = 12
125 Correct 3 ms 4588 KB Output is correct : V - N = 12
126 Correct 2 ms 4596 KB Output is correct : V - N = 12
127 Correct 3 ms 4588 KB Output is correct : V - N = 12
128 Correct 3 ms 4588 KB Output is correct : V - N = 12
129 Correct 3 ms 4588 KB Output is correct : V - N = 12
130 Correct 2 ms 4584 KB Output is correct : V - N = 12
131 Correct 2 ms 4588 KB Output is correct : V - N = 12
132 Correct 3 ms 4588 KB Output is correct : V - N = 12
133 Correct 4 ms 4588 KB Output is correct : V - N = 12
134 Correct 2 ms 4588 KB Output is correct : V - N = 12
135 Correct 3 ms 4596 KB Output is correct : V - N = 12
136 Correct 3 ms 4588 KB Output is correct : V - N = 12
137 Correct 3 ms 4588 KB Output is correct : V - N = 12
138 Correct 3 ms 4596 KB Output is correct : V - N = 12
139 Incorrect 3 ms 4596 KB Wrong Answer [12]
140 Halted 0 ms 0 KB -