Submission #420376

#	Time	Username	Problem	Language	Result	Execution time	Memory
420376		ACmachine	Airline Route Map (JOI18_airline)	C++17	0 / 100	695 ms	33332 KiB

Alice

#include <bits/stdc++.h>
#include "Alicelib.h"
#include <cassert>
#include <cstdio>
using namespace std;
#define pb push_back
#define FOR(i, j, k, l) for(int i = (j); i < (k); i+=(l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)


void Alice( int N, int M, int A[], int B[] ){ 
    vector<array<int, 2>> edges;
    REP(i, M){
        edges.pb({A[i], B[i]});
    }
    int curr = N;
    REP(i, 10){
        REP(j, N){
            if((j & (1 << i))){ // degrees of indicators will be non_increasing;       
                edges.pb({curr + i, j});
            }
        }
        if(i > 0){
            edges.pb({curr + i - 1, curr + i});
        }
    }
    // when I add 2 that go to all realgraph edges, it means that those that have deg 1 vertices hold some information; 
    curr += 10;
    REP(i, N){
        edges.pb({curr, i});
    }
    curr++;
    REP(i, N){
        edges.pb({curr, i});
    }
    edges.pb({curr, curr - 1});
    curr++;
    edges.pb({curr - 2, curr});
    curr++;
    edges.pb({curr - 2, curr}); 
    curr++;
    InitG(N + 14, (int)edges.size());
	REP(i, edges.size()){
        MakeG(i, edges[i][0], edges[i][1]);
    }
}

Bob

#include <bits/stdc++.h>
#include "Boblib.h"
#include <cassert>
#include <cstdio>
using namespace std;
#define pb push_back
#define FOR(i, j, k, l) for(int i = (j); i < (k); i+=(l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
void Bob( int V, int U, int C[], int D[] ){
    vector<array<int, 2>> edges;
    vector<vector<int>> g(V);
    vector<int> deg(V, 0);
    vector<vector<int>> mat(V, vector<int>(V, 0));
    REP(i, U){
        deg[C[i]]++;
        deg[D[i]]++;
        g[C[i]].pb(D[i]);
        g[D[i]].pb(C[i]);
        mat[C[i]][D[i]] = mat[D[i]][C[i]] = 1;
    }
    vector<int> ones;
    REP(i, V){
        if(deg[i] == 1)
            ones.pb(i);
    }
    int f = -1, s = -1;
    REP(i, ones.size()){
        REP(j, i){
            if(mat[g[ones[i]][0]][g[ones[j]][0]]){
                f = g[ones[i]][0];
                s = g[ones[j]][0];
            }
        }
    }
    vector<bool> ograph(V, false);
    vector<bool> indicator(V, true);
    indicator[f] = indicator[s] = false; 
    for(int x : g[f]){
        indicator[x] = false;  
        ograph[x] = true;
    }
    for(int x : g[s]){
        indicator[x] = false;
        ograph[x] = true;
    }
    for(int x : ones) 
        ograph[x] = false;
    ograph[s] = ograph[f] = false;
    vector<int> indicators;
    REP(i, V){
        if(indicator[i])
            indicators.pb(i);
    } 
    
    int start = indicators[0];
    vector<int> new_indicators; // in a chain order
    int pv = -1;
    int nstart = -1;
    REP(i, 9){
        nstart = -1;
        for(int x : g[start]){
            if(indicator[x] && x != pv){
                nstart = x;
                break;
            }
        }
        if(nstart != -1){
            pv = start;
            start = nstart; 
        }
        else
            break;
    }
    pv = -1;
    REP(i, 9){
        nstart = -1;
        new_indicators.pb(start);
        for(int x : g[start]){
            if(indicator[x] && x != pv){
                nstart = x;
                break;
            }
        }
        pv = start; 
        start = nstart; 
    }
    new_indicators.pb(start);
    indicators.swap(new_indicators);
    if(deg[indicators[0]] < deg[indicators.back()]){
        reverse(indicators.begin(), indicators.end()); 
    }  
    vector<int> mark(V, 0);
    REP(i, 10){
        int v = indicators[i];
        for(int x : g[v]){
            mark[x] |= (1 << i);
        }
    }
    REP(i, V){
        if(ograph[i]) cout << mark[i] << " ";
    }
    cout << "\n";
    REP(i, U){
        if(ograph[C[i]] && ograph[D[i]]){
            edges.pb({mark[C[i]], mark[D[i]]});
        }
    }
	InitMap( V - 14, (int)edges.size() );
    REP(i, edges.size()){
        MakeMap(edges[i][0], edges[i][1]);
    }	
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:7:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i+=(l))
      |                                            ^
Alice.cpp:9:19: note: in expansion of macro 'FOR'
    9 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
Alice.cpp:45:2: note: in expansion of macro 'REP'
   45 |  REP(i, edges.size()){
      |  ^~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:7:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i+=(l))
      |                                            ^
Bob.cpp:9:19: note: in expansion of macro 'FOR'
    9 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
Bob.cpp:29:5: note: in expansion of macro 'REP'
   29 |     REP(i, ones.size()){
      |     ^~~
Bob.cpp:7:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i+=(l))
      |                                            ^
Bob.cpp:9:19: note: in expansion of macro 'FOR'
    9 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
Bob.cpp:111:5: note: in expansion of macro 'REP'
  111 |     REP(i, edges.size()){
      |     ^~~

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