Submission #684827

#TimeUsernameProblemLanguageResultExecution timeMemory
684827US3RN4M3Airline Route Map (JOI18_airline)C++17
100 / 100
691 ms29264 KiB
#include "Alicelib.h" #include <cassert> #include <cstdio> #include<bits/stdc++.h> using namespace std; void Alice( int N, int M, int A[], int B[] ){ vector<pair<int, int>> ans; for(int i = 0; i < M; i++) ans.push_back({A[i], B[i]}); for(int i = 0; i < N + 12; i++) { if(i != N + 1 && i != N) ans.push_back({N, i}); } for(int i = N + 2; i < N + 12; i++) { ans.push_back({N + 1, i}); } for(int i = N + 4; i < N + 12; i++) { ans.push_back({N + 2, i}); } for(int i = N + 3; i < N + 11; i++) { ans.push_back({i, i + 1}); } for(int i = 0; i < 10; i++) { for(int j = 0; j < N; j++) if((j >> i) & 1) { ans.push_back({N + 2 + i, j}); } } InitG(N + 12, ans.size()); for(int i = 0; i < ans.size(); i++) MakeG(i, ans[i].first, ans[i].second); }
#include "Boblib.h" #include <cassert> #include <cstdio> #include<bits/stdc++.h> using namespace std; void Bob( int V, int U, int C[], int D[] ){ vector<vector<int>> graph(V); for(int i = 0; i < U; i++) { graph[C[i]].push_back(D[i]); graph[D[i]].push_back(C[i]); } int head = 0; for(int i = 0; i < V; i++) if(graph[i].size() == V - 2) head = i; int head2 = 0; vector<bool> is_head2(V, true); is_head2[head] = false; for(int i : graph[head]) is_head2[i] = false; for(int i = 0; i < V; i++) if(is_head2[i]) head2 = i; vector<bool> is_head_extra(V, false); for(int i : graph[head2]) is_head_extra[i] = true; int heads[10]; vector<int> opts; for(int i = 0; i < V; i++) if(is_head_extra[i]) opts.push_back(i); for(int i = 0; i < 10; i++) { int cnt = 0; for(int k : graph[opts[i]]) if(is_head_extra[k]) cnt++; if(cnt > 3) { heads[0] = opts[i]; break; } } is_head_extra[heads[0]] = false; vector<bool> is_head3(V, true); for(int i : graph[heads[0]]) is_head3[i] = false; for(int i : opts) if(i != heads[0] && is_head3[i]) heads[1] = i; is_head_extra[heads[1]] = false; for(int i = 1; i < 9; i++) { for(int j : graph[heads[i]]) if(is_head_extra[j]) { heads[i + 1] = j; is_head_extra[j] = false; } } vector<int> new_lable(V, 0); for(int i = 0; i < 10; i++) { for(int j : graph[heads[i]]) new_lable[j] += (1<<i); } vector<bool> is_special(V, false); for(int i : opts) is_special[i] = true; is_special[head] = true; is_special[head2] = true; vector<pair<int, int>> ans; for(int i = 0; i < U; i++) { if(is_special[C[i]] || is_special[D[i]]) continue; ans.push_back({new_lable[C[i]], new_lable[D[i]]}); } InitMap(V - 12, ans.size()); for(auto [a, b] : ans) MakeMap(a, b); }

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0; i < ans.size(); i++) MakeG(i, ans[i].first, ans[i].second);
      |                 ~~^~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:13:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |  for(int i = 0; i < V; i++) if(graph[i].size() == V - 2) head = i;
      |                                ~~~~~~~~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...