oj.uz

Submission #700116

# Submission time Handle Problem Language Result Execution time Memory
700116 2023-02-18T16:26:36 Z urosk Airline Route Map (JOI18_airline) C++14
37 / 100
 549 ms 23056 KB 
#include "Alicelib.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 1005
void Alice(ll N,ll M,ll A[],ll B[] ){
    ll n = N,m = M;
    ll d = 12;
    ll v = n+d,u = m;
    vector<pll> a;
    vector<ll> want(maxn,0);
    vector<ll> deg(maxn,0);
    vector<vector<bool> > ima(maxn,vector<bool>(maxn,0));
    for(ll i = 0;i<m;i++) a.pb({A[i],B[i]});
    for(ll i = 0;i<v-2;i++) a.pb({i,v-1});
    for(ll i = n;i<v-2;i++) a.pb({i,v-2});
    a.pb({v,n});
    set<pll> s;
    for(ll i = n;i<v-2;i++) want[i] = i-n;
    for(ll i = 0;i<v;i++) ima[i][i] = 1;
    for(ll i = v-3;i>n;i--){
        if(want[i]){
            a.pb({i,n});
            deg[i]++;
            deg[n]++;
            want[i]--;
        }
        ll j = i-1;
        while(want[i]&&j>=n){
            if(want[j]&&!ima[i][j]){
                ima[i][j] = ima[j][i] = 1;
                a.pb({i,j});
                want[j]--;
                want[i]--;
                deg[i]++;
                deg[j]++;
            }
            j--;
        }
    }
    //ceri(deg,n,v-3);
    for(ll i = 0;i<n;i++){
        for(ll j = 0;j<d-2;j++){
            if((1<<j)&i) a.pb({i,n+j});
        }
    }
    u = sz(a);
    InitG(v+1,u);
    //dbg(sz(a));
    //for(pll p : a) cerr<<p.fi<< " "<<p.sc<<endl;
    for(ll i = 0;i<u;i++) MakeG(i,a[i].fi,a[i].sc);
}
/**
4 3
0 1
0 2
0 3
**/

#include "Boblib.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 2505
void Bob(ll V,ll U,ll C[],ll D[]){
    ll n = V,m = U;
    vector<ll> ans(maxn,0);
    vector<ll> deg(maxn,0);
    vector<pll> e(maxn);
    vector<bool> spec(maxn,0);
    vector<vector<ll> > g(maxn);
    vector<vector<bool> > ok(maxn,vector<bool>(maxn,0));
    for(ll i = 0;i<m;i++) e[i] = {C[i],D[i]};
    for(ll i = 0;i<m;i++){
        ll x = e[i].fi,y = e[i].sc;
        deg[x]++;
        deg[y]++;
        ok[x][y] = ok[y][x] = 1;
        g[x].pb(y);
        g[y].pb(x);
    }
    for(ll i = 0;i<n;i++) ok[i][i] = 1;
    ll u = 0;
    for(ll i = 0;i<n;i++) if(deg[i]>deg[u]) u = i;
    ll v = -1;
    for(ll i = 0;i<n;i++) if(!ok[u][i]){
        if(v==-1) v = i;
        else if(deg[i]>deg[v]) v = i;
    }
    ll r = -1;
    for(ll i = 0;i<n;i++){
        if(!ok[u][i]&&deg[i]<deg[v]) r = i;
    }
    vector<ll> w;
    for(ll x : g[v]){
        w.pb(x);
        spec[x] = 1;
    }
    spec[u] = spec[v] = spec[r] = 1;
    for(ll x : w){
        ll cnt = -1;
        for(ll y : w){
            if(ok[x][y]){
                cnt++;
            }
        }
        if(cnt==5){
            if(ok[x][r]) cnt = 0;
        }
        for(ll y : g[x]){
            if(!spec[y]){
                ans[y]+=(1<<cnt);
            }
        }
    }
    ll gr = 0;
    for(ll i = 0;i<m;i++){
        ll x = e[i].fi,y = e[i].sc;
        if(spec[x]||spec[y]) continue;
        gr++;
    }
    InitMap(n-13,gr);
    for(ll i = 0;i<m;i++){
        ll x = e[i].fi,y = e[i].sc;
        if(spec[x]||spec[y]) continue;
        x = ans[x],y = ans[y];
        MakeMap(x,y);
    }
}
/**
4 3
0 1
0 2
0 3
**/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5800 KB Output is correct
2 Correct 3 ms 5832 KB Output is correct
3 Correct 3 ms 5896 KB Output is correct
4 Correct 3 ms 5888 KB Output is correct
5 Correct 4 ms 5892 KB Output is correct
6 Correct 3 ms 5892 KB Output is correct
7 Correct 3 ms 5900 KB Output is correct
8 Correct 3 ms 5900 KB Output is correct
9 Correct 2 ms 5892 KB Output is correct
10 Correct 3 ms 5880 KB Output is correct
11 Correct 3 ms 5892 KB Output is correct
12 Correct 3 ms 5896 KB Output is correct
13 Correct 3 ms 5892 KB Output is correct
14 Correct 3 ms 5788 KB Output is correct
15 Correct 3 ms 5900 KB Output is correct
16 Correct 3 ms 5896 KB Output is correct
17 Correct 3 ms 5892 KB Output is correct
18 Correct 3 ms 5892 KB Output is correct
19 Correct 3 ms 5892 KB Output is correct
20 Correct 3 ms 5888 KB Output is correct
21 Correct 4 ms 5892 KB Output is correct
22 Correct 2 ms 5892 KB Output is correct
23 Correct 3 ms 5900 KB Output is correct
24 Correct 3 ms 5896 KB Output is correct
25 Correct 3 ms 5896 KB Output is correct
26 Correct 3 ms 5892 KB Output is correct
27 Correct 3 ms 5900 KB Output is correct
28 Correct 3 ms 5896 KB Output is correct
29 Correct 3 ms 5892 KB Output is correct
30 Correct 3 ms 5872 KB Output is correct
31 Correct 3 ms 5888 KB Output is correct
32 Correct 3 ms 5888 KB Output is correct
33 Correct 3 ms 5888 KB Output is correct
34 Correct 3 ms 5888 KB Output is correct
35 Correct 3 ms 5920 KB Output is correct
36 Correct 3 ms 5820 KB Output is correct
37 Correct 3 ms 5872 KB Output is correct
38 Correct 3 ms 5868 KB Output is correct
39 Correct 3 ms 5900 KB Output is correct
40 Correct 4 ms 5792 KB Output is correct
41 Correct 3 ms 5868 KB Output is correct
42 Correct 3 ms 5900 KB Output is correct
43 Correct 3 ms 5892 KB Output is correct
44 Correct 3 ms 5896 KB Output is correct
45 Correct 3 ms 5904 KB Output is correct
46 Correct 3 ms 5892 KB Output is correct
47 Correct 3 ms 5792 KB Output is correct
48 Correct 3 ms 5892 KB Output is correct
49 Correct 3 ms 5892 KB Output is correct
50 Correct 3 ms 5888 KB Output is correct
51 Correct 3 ms 5896 KB Output is correct
52 Correct 3 ms 5900 KB Output is correct
53 Correct 3 ms 5888 KB Output is correct
54 Correct 3 ms 5900 KB Output is correct
55 Correct 3 ms 5892 KB Output is correct
56 Correct 3 ms 5872 KB Output is correct
57 Correct 3 ms 5892 KB Output is correct
58 Correct 3 ms 5888 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 549 ms 23056 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -