Submission #119103

#	Time	Username	Problem	Language	Result	Execution time	Memory
119103		TAISA_	Airline Route Map (JOI18_airline)	C++14	100 / 100	758 ms	29660 KiB

Alice

#include <bits/stdc++.h>
#include "Alicelib.h"
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
void Alice(int N, int M, int A[], int B[]) {
    vector<P> v;
    int s = N + 10, t = N + 11;
    for(int i = 0; i < N; i++) {
        v.push_back(P(i, s));
        for(int j = 0; j < 10; j++) {
            if((i >> j) & 1) {
                v.push_back(P(i, N + j));
            }
        }
    }
    for(int i = 0; i < 10; i++) {
        v.push_back(P(N + i, s));
        v.push_back(P(N + i, t));
        if(i < 9) {
            v.push_back(P(N + i, N + i + 1));
        }
    }
    InitG(N + 12, M + v.size());
    for(int i = 0; i < M; i++) {
        MakeG(i, A[i], B[i]);
    }
    for(int i = 0; i < v.size(); i++) {
        MakeG(M + i, v[i].first, v[i].second);
    }
}

Bob

#include <bits/stdc++.h>
#include "Boblib.h"
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
void Bob(int V, int U, int C[], int D[]) {
    vector<vector<int>> v(V);
    for(int i = 0; i < U; i++) {
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
    }
    int s, t;
    for(int i = 0; i < V; i++) {
        if(v[i].size() == V - 2) {
            vector<int> vis(V);
            vis[i] = 1;
            for(auto& e : v[i]) {
                vis[e] = 1;
            }
            for(int j = 0; j < V; j++) {
                if(!vis[j] && v[j].size() == 10) {
                    t = j;
                    break;
                }
            }
            s = i;
            break;
        }
    }
    vector<int> to(V), ts, vs(V);
    for(auto& i : v[t]) {
        to[i] = 1;
    }
    int i1 = -1, i2;
    for(auto& i : v[t]) {
        int c = 0;
        for(auto& e : v[i]) {
            if(e == t) {
                continue;
            }
            if(to[e]) {
                c++;
            }
        }
        if(c == 1) {
            if(i1 == -1) {
                i1 = i;
            } else {
                i2 = i;
            }
        }
    }
    int st;
    if(v[i1].size() > v[i2].size()) {
        st = i1;
    } else {
        st = i2;
    }
    for(int i = 0; i < 10; i++) {
        ts.push_back(st);
        vs[st] = 1;
        if(i == 9) {
            break;
        }
        int tmp;
        for(auto& e : v[st]) {
            if(to[e] && !vs[e]) {
                tmp = e;
                break;
            }
        }
        st = tmp;
    }
    vector<int> num(V, -1);
    for(int i = 0; i < 10; i++) {
        for(auto& e : v[ts[i]]) {
            if(e == t || e == s || to[e]) {
                continue;
            }
            num[e] = max(0, num[e]);
            num[e] += (1 << i);
        }
    }
    for(int i = 0; i < V; i++) {
        if(i == s || i == t || to[i] || num[i] != -1) {
            continue;
        }
        num[i] = 0;
        break;
    }
    vector<P> es;
    for(int i = 0; i < V; i++) {
        if(num[i] == -1) {
            continue;
        }
        for(auto& e : v[i]) {
            if(e == s || to[e]) {
                continue;
            }
            if(num[i] < num[e]) {
                es.push_back(P(num[i], num[e]));
            }
        }
    }
    InitMap(V - 12, es.size());
    for(auto p : es) {
        MakeMap(p.first, p.second);
    }
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++) {
                    ~~^~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:15:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v[i].size() == V - 2) {
            ~~~~~~~~~~~~^~~~~~~~
Bob.cpp:86:24: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(i == s || i == t || to[i] || num[i] != -1) {
                      ~~^~~~
Bob.cpp:86:14: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(i == s || i == t || to[i] || num[i] != -1) {
            ~~^~~~
Bob.cpp:73:12: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
         st = tmp;
         ~~~^~~~~
Bob.cpp:55:27: warning: 'i2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(v[i1].size() > v[i2].size()) {
                           ^

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