oj.uz

Submission #700117

# Submission time Handle Problem Language Result Execution time Memory
700117 2023-02-18T16:27:46 Z urosk Airline Route Map (JOI18_airline) C++14
0 / 100
 650 ms 28752 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 2505
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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6636 KB Output is correct
2 Correct 5 ms 6660 KB Output is correct
3 Correct 3 ms 6664 KB Output is correct
4 Correct 3 ms 6636 KB Output is correct
5 Correct 3 ms 6672 KB Output is correct
6 Correct 3 ms 6664 KB Output is correct
7 Correct 3 ms 6648 KB Output is correct
8 Correct 4 ms 6664 KB Output is correct
9 Correct 4 ms 6656 KB Output is correct
10 Correct 3 ms 6588 KB Output is correct
11 Correct 3 ms 6660 KB Output is correct
12 Correct 3 ms 6588 KB Output is correct
13 Correct 3 ms 6588 KB Output is correct
14 Correct 3 ms 6664 KB Output is correct
15 Correct 3 ms 6664 KB Output is correct
16 Correct 3 ms 6512 KB Output is correct
17 Correct 5 ms 6640 KB Output is correct
18 Correct 4 ms 6664 KB Output is correct
19 Correct 3 ms 6640 KB Output is correct
20 Correct 4 ms 6660 KB Output is correct
21 Correct 3 ms 6588 KB Output is correct
22 Correct 3 ms 6644 KB Output is correct
23 Correct 3 ms 6664 KB Output is correct
24 Correct 3 ms 6712 KB Output is correct
25 Correct 3 ms 6660 KB Output is correct
26 Correct 3 ms 6600 KB Output is correct
27 Correct 3 ms 6588 KB Output is correct
28 Correct 3 ms 6660 KB Output is correct
29 Correct 3 ms 6660 KB Output is correct
30 Correct 4 ms 6644 KB Output is correct
31 Correct 3 ms 6660 KB Output is correct
32 Correct 4 ms 6600 KB Output is correct
33 Correct 3 ms 6652 KB Output is correct
34 Correct 3 ms 6656 KB Output is correct
35 Correct 3 ms 6656 KB Output is correct
36 Correct 3 ms 6660 KB Output is correct
37 Correct 3 ms 6664 KB Output is correct
38 Correct 4 ms 6644 KB Output is correct
39 Correct 3 ms 6664 KB Output is correct
40 Correct 4 ms 6660 KB Output is correct
41 Correct 4 ms 6576 KB Output is correct
42 Correct 3 ms 6636 KB Output is correct
43 Correct 3 ms 6660 KB Output is correct
44 Correct 4 ms 6660 KB Output is correct
45 Correct 3 ms 6668 KB Output is correct
46 Correct 3 ms 6640 KB Output is correct
47 Correct 3 ms 6660 KB Output is correct
48 Correct 3 ms 6664 KB Output is correct
49 Correct 3 ms 6660 KB Output is correct
50 Correct 3 ms 6668 KB Output is correct
51 Runtime error 5 ms 8836 KB Execution killed with signal 11
52 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6636 KB Output is correct
2 Correct 5 ms 6660 KB Output is correct
3 Correct 3 ms 6664 KB Output is correct
4 Correct 3 ms 6636 KB Output is correct
5 Correct 3 ms 6672 KB Output is correct
6 Correct 3 ms 6664 KB Output is correct
7 Correct 3 ms 6648 KB Output is correct
8 Correct 4 ms 6664 KB Output is correct
9 Correct 4 ms 6656 KB Output is correct
10 Correct 3 ms 6588 KB Output is correct
11 Correct 3 ms 6660 KB Output is correct
12 Correct 3 ms 6588 KB Output is correct
13 Correct 3 ms 6588 KB Output is correct
14 Correct 3 ms 6664 KB Output is correct
15 Correct 3 ms 6664 KB Output is correct
16 Correct 3 ms 6512 KB Output is correct
17 Correct 5 ms 6640 KB Output is correct
18 Correct 4 ms 6664 KB Output is correct
19 Correct 3 ms 6640 KB Output is correct
20 Correct 4 ms 6660 KB Output is correct
21 Correct 3 ms 6588 KB Output is correct
22 Correct 3 ms 6644 KB Output is correct
23 Correct 3 ms 6664 KB Output is correct
24 Correct 3 ms 6712 KB Output is correct
25 Correct 3 ms 6660 KB Output is correct
26 Correct 3 ms 6600 KB Output is correct
27 Correct 3 ms 6588 KB Output is correct
28 Correct 3 ms 6660 KB Output is correct
29 Correct 3 ms 6660 KB Output is correct
30 Correct 4 ms 6644 KB Output is correct
31 Correct 3 ms 6660 KB Output is correct
32 Correct 4 ms 6600 KB Output is correct
33 Correct 3 ms 6652 KB Output is correct
34 Correct 3 ms 6656 KB Output is correct
35 Correct 3 ms 6656 KB Output is correct
36 Correct 3 ms 6660 KB Output is correct
37 Correct 3 ms 6664 KB Output is correct
38 Correct 4 ms 6644 KB Output is correct
39 Correct 3 ms 6664 KB Output is correct
40 Correct 4 ms 6660 KB Output is correct
41 Correct 4 ms 6576 KB Output is correct
42 Correct 3 ms 6636 KB Output is correct
43 Correct 3 ms 6660 KB Output is correct
44 Correct 4 ms 6660 KB Output is correct
45 Correct 3 ms 6668 KB Output is correct
46 Correct 3 ms 6640 KB Output is correct
47 Correct 3 ms 6660 KB Output is correct
48 Correct 3 ms 6664 KB Output is correct
49 Correct 3 ms 6660 KB Output is correct
50 Correct 3 ms 6668 KB Output is correct
51 Runtime error 5 ms 8836 KB Execution killed with signal 11
52 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

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