Submission #482062

#	Time	Username	Problem	Language	Result	Execution time	Memory
482062		leaked	Airline Route Map (JOI18_airline)	C++14	0 / 100	742 ms	21080 KiB

Alice

#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);
}

Bob

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 63