oj.uz

Submission #482063

# Submission time Handle Problem Language Result Execution time Memory
482063 2021-10-22T21:46:52 Z leaked Airline Route Map (JOI18_airline) C++14
0 / 100
 737 ms 21220 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;
            int sh=-1;
            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){
                    if(kk){
                        kk=0;
                        break;
                    }
                    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);
//                    }
                    sh=v;
                    start[i]=0;
                    kk=1;
//                    if(kk)
//                    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(u==sh) continue;
                            if(bad[u] && (sz(path)==1 || path[sz(path)-2]!=u)){
                                path.pb(u);
                                break;
                            }
                        }
                    }
//                    debug()<<imie(path);
                }
            }
            vec<bool>u(V,0);
            for(auto &z : path){
                if(u[z]) kk=0;
                u[z]=1;
//                if(u[z])
            }
            if(!kk) continue;
            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 1 ms 4516 KB Output is correct
2 Correct 2 ms 4596 KB Output is correct
3 Correct 2 ms 4588 KB Output is correct
4 Correct 2 ms 4592 KB Output is correct
5 Correct 1 ms 4588 KB Output is correct
6 Correct 2 ms 4588 KB Output is correct
7 Correct 1 ms 4588 KB Output is correct
8 Correct 1 ms 4596 KB Output is correct
9 Correct 3 ms 4588 KB Output is correct
10 Correct 2 ms 4592 KB Output is correct
11 Correct 2 ms 4588 KB Output is correct
12 Correct 2 ms 4596 KB Output is correct
13 Correct 3 ms 4588 KB Output is correct
14 Correct 2 ms 4588 KB Output is correct
15 Correct 2 ms 4588 KB Output is correct
16 Correct 2 ms 4592 KB Output is correct
17 Correct 2 ms 4568 KB Output is correct
18 Correct 3 ms 4588 KB Output is correct
19 Incorrect 2 ms 4588 KB Wrong Answer [12]
20 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 20964 KB Output is correct : V - N = 12
2 Correct 537 ms 18296 KB Output is correct : V - N = 12
3 Correct 133 ms 10408 KB Output is correct : V - N = 12
4 Correct 9 ms 5056 KB Output is correct : V - N = 12
5 Correct 132 ms 8052 KB Output is correct : V - N = 12
6 Correct 481 ms 16792 KB Output is correct : V - N = 12
7 Correct 491 ms 20932 KB Output is correct : V - N = 12
8 Correct 704 ms 19548 KB Output is correct : V - N = 12
9 Correct 318 ms 12140 KB Output is correct : V - N = 12
10 Correct 34 ms 5660 KB Output is correct : V - N = 12
11 Correct 65 ms 6336 KB Output is correct : V - N = 12
12 Correct 365 ms 13976 KB Output is correct : V - N = 12
13 Correct 625 ms 20380 KB Output is correct : V - N = 12
14 Correct 468 ms 20456 KB Output is correct : V - N = 12
15 Correct 360 ms 15920 KB Output is correct : V - N = 12
16 Correct 61 ms 7160 KB Output is correct : V - N = 12
17 Correct 18 ms 5380 KB Output is correct : V - N = 12
18 Correct 264 ms 11316 KB Output is correct : V - N = 12
19 Correct 599 ms 19160 KB Output is correct : V - N = 12
20 Correct 657 ms 20908 KB Output is correct : V - N = 12
21 Correct 123 ms 10012 KB Output is correct : V - N = 12
22 Correct 121 ms 8264 KB Output is correct : V - N = 12
23 Correct 41 ms 6264 KB Output is correct : V - N = 12
24 Correct 4 ms 4844 KB Output is correct : V - N = 12
25 Correct 35 ms 5624 KB Output is correct : V - N = 12
26 Correct 84 ms 7892 KB Output is correct : V - N = 12
27 Correct 192 ms 9000 KB Output is correct : V - N = 12
28 Correct 173 ms 8548 KB Output is correct : V - N = 12
29 Correct 91 ms 6716 KB Output is correct : V - N = 12
30 Correct 7 ms 5040 KB Output is correct : V - N = 12
31 Correct 6 ms 4844 KB Output is correct : V - N = 12
32 Correct 7 ms 4836 KB Output is correct : V - N = 12
33 Correct 7 ms 4964 KB Output is correct : V - N = 12
34 Correct 6 ms 4900 KB Output is correct : V - N = 12
35 Correct 7 ms 4752 KB Output is correct : V - N = 12
36 Correct 737 ms 20976 KB Output is correct : V - N = 12
37 Correct 489 ms 21220 KB Output is correct : V - N = 12
38 Correct 690 ms 20920 KB Output is correct : V - N = 12
39 Correct 556 ms 21064 KB Output is correct : V - N = 12
40 Correct 718 ms 21084 KB Output is correct : V - N = 12
41 Correct 87 ms 7916 KB Output is correct : V - N = 12
42 Correct 89 ms 7240 KB Output is correct : V - N = 12
43 Correct 122 ms 7664 KB Output is correct : V - N = 12
44 Correct 7 ms 4972 KB Output is correct : V - N = 12
45 Correct 67 ms 6504 KB Output is correct : V - N = 12
46 Correct 267 ms 10772 KB Output is correct : V - N = 12
47 Correct 111 ms 8040 KB Output is correct : V - N = 12
48 Correct 324 ms 12192 KB Output is correct : V - N = 12
49 Correct 49 ms 6260 KB Output is correct : V - N = 12
50 Correct 22 ms 5404 KB Output is correct : V - N = 12
51 Correct 344 ms 18236 KB Output is correct : V - N = 12
52 Correct 7 ms 4988 KB Output is correct : V - N = 12
53 Correct 355 ms 16932 KB Output is correct : V - N = 12
54 Correct 587 ms 19276 KB Output is correct : V - N = 12
55 Correct 26 ms 5784 KB Output is correct : V - N = 12
56 Correct 317 ms 13528 KB Output is correct : V - N = 12
57 Correct 601 ms 20252 KB Output is correct : V - N = 12
58 Correct 65 ms 7016 KB Output is correct : V - N = 12
59 Correct 174 ms 11336 KB Output is correct : V - N = 12
60 Correct 456 ms 20456 KB Output is correct : V - N = 12
61 Correct 2 ms 4588 KB Output is correct : V - N = 12
62 Correct 3 ms 4588 KB Output is correct : V - N = 12
63 Correct 2 ms 4600 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 2 ms 4600 KB Output is correct : V - N = 12
67 Incorrect 3 ms 4588 KB Wrong Answer [12]
68 Halted 0 ms 0 KB -