Submission #91499

#	Time	Username	Problem	Language	Result	Execution time	Memory
91499		igzi	Airline Route Map (JOI18_airline)	C++17	100 / 100	740 ms	30832 KiB

Alice

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

using namespace std;

void Alice(int n, int m, int a[], int b[]){
vector <pair<int,int>> v;
int i,j,tmp;
for(i=0;i<m;i++){
    v.push_back({a[i],b[i]});
}
for(i=0;i<n;i++){
    tmp=i;
    j=0;
    while(tmp>0){
        if(tmp%2) v.push_back({i,n+j});
        tmp/=2;
        j++;
    }
}
for(i=0;i<n+10;i++){
    v.push_back({i,n+10});
}
for(i=n;i<n+10;i++){
v.push_back({i,n+11});
if(i!=n+9) v.push_back({i,i+1});
}
v.push_back({n,n+2});
v.push_back({n,n+3});
v.push_back({n,n+4});
InitG(n+12,v.size());
for(i=0;i<v.size();i++){
MakeG(i,v[i].first,v[i].second);
}
}

Bob

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

using namespace std;

vector <int> v,adj[maxN];
bool k[maxN];

void dfs(int n){
v.push_back(n);
k[n]=false;
int i;
for(i=0;i<adj[n].size();i++){
if(k[adj[n][i]]){
    dfs(adj[n][i]);
}
}
}

void Bob(int n, int m, int a[], int b[]){
int i,j,id,tmp,pom,p[maxN];
int ar[maxN],deg[maxN];
for(i=0;i<m;i++){
    adj[a[i]].push_back(b[i]);
    adj[b[i]].push_back(a[i]);
}
for(i=0;i<n;i++){
    if(adj[i].size()==n-2) id=i;
}
tmp=id;
for(i=0;i<n;i++){
    if(i==id) continue;
    bool x=false;
    for(j=0;j<adj[i].size();j++){
        if(adj[i][j]==id) {x=true; break;}
    }
    if(!x) break;
}
id=i;
for(i=0;i<adj[id].size();i++) k[adj[id][i]]=true;
for(i=0;i<adj[id].size();i++){
    pom=0;
    for(j=0;j<adj[adj[id][i]].size();j++){
        if(k[adj[adj[id][i]][j]]) pom++;
    }
    deg[adj[id][i]]=pom;
}
for(i=0;i<adj[id].size();i++){
    if(deg[adj[id][i]]==4){
        v.push_back(adj[id][i]);
        k[adj[id][i]]=false;
    }
    if(deg[adj[id][i]]==1) pom=adj[id][i];
}
dfs(pom);
reverse(v.begin()+1,v.end());
for(i=0;i<v.size();i++) {k[v[i]]=true; ar[v[i]]=i;}
for(i=0;i<n;i++){
    if(k[i] || i==id || i==tmp) continue;
    pom=0;
    for(j=0;j<adj[i].size();j++){
        if(k[adj[i][j]]){
            pom+=(1<<ar[adj[i][j]]);
        }
    }
    p[i]=pom;
}
vector <pair<int,int>> u;
for(i=0;i<m;i++){
    if(k[a[i]] || a[i]==id || a[i]==tmp || k[b[i]] || b[i]==id || b[i]==tmp) continue;
    u.push_back({p[a[i]],p[b[i]]});
}
InitMap(n-12,u.size());
for(i=0;i<u.size();i++) MakeMap(u[i].first,u[i].second);
}

Compilation message (stderr)

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

Bob.cpp: In function 'void dfs(int)':
Bob.cpp:14:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[n].size();i++){
         ~^~~~~~~~~~~~~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:29:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(adj[i].size()==n-2) id=i;
        ~~~~~~~~~~~~~^~~~~
Bob.cpp:35:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<adj[i].size();j++){
             ~^~~~~~~~~~~~~~
Bob.cpp:41:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[id].size();i++) k[adj[id][i]]=true;
         ~^~~~~~~~~~~~~~~
Bob.cpp:42:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[id].size();i++){
         ~^~~~~~~~~~~~~~~
Bob.cpp:44:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<adj[adj[id][i]].size();j++){
             ~^~~~~~~~~~~~~~~~~~~~~~~
Bob.cpp:49:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[id].size();i++){
         ~^~~~~~~~~~~~~~~
Bob.cpp:58:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<v.size();i++) {k[v[i]]=true; ar[v[i]]=i;}
         ~^~~~~~~~~
Bob.cpp:62:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<adj[i].size();j++){
             ~^~~~~~~~~~~~~~
Bob.cpp:75:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<u.size();i++) MakeMap(u[i].first,u[i].second);
         ~^~~~~~~~~
Bob.cpp:56:4: warning: 'pom' may be used uninitialized in this function [-Wmaybe-uninitialized]
 dfs(pom);
 ~~~^~~~~
Bob.cpp:71:64: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(k[a[i]] || a[i]==id || a[i]==tmp || k[b[i]] || b[i]==id || b[i]==tmp) continue;
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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