Submission #1119680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119680		thangdz2k7	Airline Route Map (JOI18_airline)	C++17	0 / 100	517 ms	23436 KiB

Alice

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

using namespace std;

// grader

//void InitG(int N, int M){
//    cout << N << ' ' << M << endl;
//}
//
//void MakeG(int pos, int u, int v){
//    cout << u << ' ' << v << endl;
//}

// end

void Alice(int N, int M, int *A, int *B){
    vector <bool> used(N, 0);
    vector <pair <int, int>> edge;
    edge.emplace_back(N - 1, N);

    for (int i = 0; i < M; ++ i){
        if (A[i] > B[i]) swap(A[i], B[i]);
        edge.emplace_back(A[i], B[i]);
        if (A[i] + 1 == B[i]) used[A[i]] = 1;
    }

    for (int i = 0; i < N - 1; ++ i) if (!used[i]) {
        edge.emplace_back(i, i + 1);
        edge.emplace_back(i, N);
    }

    int m = edge.size();

    InitG(N + 1, m);
    for (int i = 0; i < m; ++ i)
        MakeG(i, edge[i].first, edge[i].second);

}

//int main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    int n, m; cin >> n >> m;
//    vector <int> u(m), v(m);
//    for (int i = 0; i < m; ++ i)
//        cin >> u[i] >> v[i];
//
//    Alice(n, m, u, v);
//}

Bob

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

using namespace std;

// grader

//void InitMap(int N, int M){
//    cout << N << ' ' << M << endl;
//}
//
//void MakeMap(int u, int v){
//    cout << u << ' ' << v << endl;
//}

// end

void Bob(int N, int M, int *C, int *D){
    vector <int> deg(N, 0);
    vector <vector <int>> adj(N);
    for (int i = 0; i < M; ++ i) {
        deg[D[i]] ++;
        adj[C[i]].push_back(D[i]);
    }

    queue <int> qu;
    for (int i = 0; i < N; ++ i)
        if (!deg[i]) qu.push(i);

    vector <int> ord(N);
    int tot = 0;
    while (qu.size()){
        int u = qu.front();
        qu.pop();
        ord[u] = tot ++;

        for (int v : adj[u])
            if (!--deg[v]) qu.push(v);
    }

    vector <pair <int, int>> edge;
    vector <bool> used(N, 0);
    for (int i = 0; i < M; ++ i){
        if (ord[D[i]] == N - 1) used[ord[C[i]]] = 1;
        else if (ord[C[i]] + 1 < ord[D[i]])
            edge.emplace_back(ord[C[i]], ord[D[i]]);
    }

    for (int i = 0; i < N - 1; ++ i)
        if (!used[i]) edge.emplace_back(i, i + 1);

    int m = edge.size();

    InitMap(N - 1, m);
    for (auto [A, B] : edge) MakeMap(A, B);
}

//int main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    srand(time(NULL));
//
//    int n, m; cin >> n >> m;
//    vector <int> u(m), v(m);
//    for (int i = 0; i < m; ++ i) cin >> u[i] >> v[i];
//
//    vector <int> pv(n), pe(m);
//    iota(pv.begin(), pv.end(), 0);
//    iota(pe.begin(), pe.end(), 0);
//    random_shuffle(pv.begin(), pv.end());
//    random_shuffle(pe.begin(), pe.end());
//
//    vector <int> c(m), d(m);
//    for (int i = 0; i < m; ++ i) {
//        int id = pe[i];
//        c[i] = pv[u[id]];
//        d[i] = pv[v[id]];
//    }
//
//    Bob(n, m, c, d);
//}

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