Submission #46417

#	Time	Username	Problem	Language	Result	Execution time	Memory
46417		Alexa2001	Airline Route Map (JOI18_airline)	C++17	0 / 100	702 ms	24496 KiB

Alice

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

void Alice( int N, int M, int A[], int B[] )
{
    bool edge[1003][1003];
    memset(edge, 0, sizeof(edge));
    int i, cnt = 0;
    for(i=0; i<M; ++i)
        edge[A[i]][B[i]] = edge[B[i]][A[i]] = 1, ++cnt;

    for(i=0; i<N-1; ++i)
        if(!edge[i][i+1])
        {
            edge[i][i+1] = 1;
            cnt += 2;
            edge[i][N] = 1;
        }
    ++cnt, edge[N-1][N] = 1;

    InitG(N+1, cnt);
    cnt = 0;
    int j;
    for(i=0; i<=N; ++i)
        for(j=i+1; j<=N; ++j)
            if(edge[i][j]) MakeG(cnt++, i, j);
}

Bob

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

const int Nmax = 1003;
using namespace std;

static vector<int> v[Nmax], ord;
static bool used[Nmax], edge[Nmax][Nmax], bad[Nmax];
static int where[Nmax];

static void dfs(int node)
{
    used[node] = 1;
    for(auto it : v[node])
        if(!used[it]) dfs(it);
    ord.push_back(node);
}

void Bob( int n, int m, int C[], int D[] )
{
    int i, j;
    for(i=0; i<m; ++i)
        v[C[i]].push_back(D[i]);

    for(i=0; i<n; ++i)
        if(!used[i]) dfs(i);

    reverse(ord.begin(), ord.end());
    for(i=0; i<n; ++i) where[ord[i]] = i;

    for(i=0; i<n; ++i)
        for(auto it : v[i])
            if(it == ord.back()) bad[i] = 1;

    int cnt = 0;
    for(i=0; i<n; ++i)
        for(auto z : v[i])
            if( !(where[i] == where[z] - 1 && bad[i]) && !(where[z] == where[i] - 1 && bad[z]) )
                if(where[i] != n-1 && where[z] != n-1)
                    edge[where[i]][where[z]] = edge[where[z]][where[i]] = 1, ++cnt;

    InitMap(n-1, cnt);
    for(i=0; i<n-1; ++i)
        for(j=i+1; j<n-1; ++j)
            if(edge[i][j]) MakeMap(i, j);
}

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