Submission #1247569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247569		AHOKA	Airline Route Map (JOI18_airline)	C++20	0 / 100	148 ms	23112 KiB

Alice

#include <bits/stdc++.h>
#include "Alicelib.h"

#pragma GCC target("sse4")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
//#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc + 1)

const int maxn = 1e3, maxm = 1e4, lg = 10, oo = 1e15;

int n, m, nn;

int id[maxn];

vector<pii> e;

void prep(){
    int j = 1;
    for (int i = 0; i < maxn;i++){
        while (__builtin_popcount(j) <= 1)
            j++;
        id[i] = j;
    }
}

void Alice(int N, int M, int A[], int B[]) {
    prep();

    n = N;
    m = M;

    for (int i = 0; i < m; i++)
        e.push_back({A[i], B[i]});

    // d[nn - 1] = 1;

    nn = n - 1 + lg + 2;

    e.push_back({nn - 1, nn});

    for (int b = 0; b < lg;b++)
        e.push_back({n + b, nn});

    for (int b = 1; b < lg; b++)
        e.push_back({n + b - 1, n + b});

    for (int b = 2; b < lg; b++)
        e.push_back({n, n + b});

    for (int i = 0; i < n;i++)
        for (int b = 0; b < lg;b++) 
            if(id[i] & (1ll << b))
                e.push_back({i, n + b});

    InitG(nn + 1, e.size());
    for (int i = 0; i < e.size(); i++)
        MakeG(i, e[i].F, e[i].S);
}

Bob

#include <bits/stdc++.h>
#include "Boblib.h"

#pragma GCC target("sse4")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
//#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc + 1)

const int maxn = 1e3, maxm = 1e4, lg = 10, oo = 1e15;

int n, m, nn;

int id[maxn], rev[maxn];

vector<int> adj[maxn];

vector<pii> e[2];

bool bt[maxn];

int w[maxn];

void prep(){
    int j = 1;
    for (int i = 0; i < maxn;i++){
        
        while (__builtin_popcount(j) <= 1)
            j++;
            
        rev[j] = i;
    }
}

void Bob(int V, int U, int C[], int D[]) {
    prep();

    n = V;
    m = U;

    for (int i = 0; i < m; i++) {
		int u = C[i], v = D[i];
		adj[u].push_back(v); adj[v].push_back(u);
		e[0].push_back({u, v});
	}

    int d1 = 0;
    for (int i = 0; i < n; i++)
        if (adj[i].size() == 1)
            d1 = i;

    int db = adj[d1].back();

    for(auto v : adj[db])
        if(v ^ d1)
            bt[v] = 1;

	for (int i = 0; i < n; i++)
        adj[i].clear();

    for (auto [u, v] : e[0])
		if (bt[u] && bt[v]) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

    int b0 = 0;
    for (int i = 0; i < n;i++)
        if(adj[i].size() > adj[b0].size())
            b0 = i;

    w[b0] = 1;

    int mxb = 0;
    for (int i = 0; i < n;i++)
        if(adj[i].size() == 2)
            mxb = i;

    w[mxb] = (1ll << (lg - 1));
    for (int b = lg - 2; b;b--)
        for(auto v : adj[mxb])
            if(!w[v]){
                mxb = v;
                w[mxb] = (1ll << b);
                break;
            }

    for (int i = 0; i < n;i++){
        if(!w[i] && (i ^ d1) && (i ^ db)){
            for (auto u : adj[i])
                if(w[u])
                    id[i] += w[u];
            id[i] = rev[id[i]];
        }
    }

    w[d1] = w[db] = 1;

    for(auto [u, v] : e[0])
        if (!w[u] && !w[v])
            e[1].push_back({id[u], id[v]});


	InitMap(n - lg - 2, e[1].size());
	for (int i = 0; i < e[1].size(); i++)
        MakeMap(e[1][i].F, e[1][i].S);
}

Compilation message (stderr)

# 1번째 컴파일 단계

Alice.cpp:21:49: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   21 | const int maxn = 1e3, maxm = 1e4, lg = 10, oo = 1e15;
      |                                                 ^~~~

# 2번째 컴파일 단계

Bob.cpp:21:49: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   21 | const int maxn = 1e3, maxm = 1e4, lg = 10, oo = 1e15;
      |                                                 ^~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 15
• Subtask 3: 0 / 63