oj.uz

Submission #46417

# Submission time Handle Problem Language Result Execution time Memory
46417 2018-04-20T07:06:39 Z Alexa2001 Airline Route Map (JOI18_airline) C++17
0 / 100
 702 ms 24496 KB 
#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);
}


#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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8640 KB Output is correct
2 Incorrect 7 ms 8696 KB Wrong Answer [11]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8640 KB Output is correct
2 Incorrect 7 ms 8696 KB Wrong Answer [11]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 702 ms 24496 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -