Submission #991804

#TimeUsernameProblemLanguageResultExecution timeMemory
991804danikoynovAirline Route Map (JOI18_airline)C++14
68 / 100
436 ms72436 KiB
#include "Alicelib.h" #include <cassert> #include <cstdio> #include<bits/stdc++.h> using namespace std; const int maxn = 2e3 + 10; const int maxbit = 11; const int fict = 15; /** from 0 to N - 1 : normal vertexes from N to N + maxbit - 1 : binary powers from N + maxbit to N + maxbit + fict - 1 : fictitious vertexes vertex N + maxbit is connected to all except the binary powers */ void Alice( int N, int M, int A[], int B[] ) { if (N == 1 && M == 0) { InitG(1, 0); return; } vector < pair < int, int > > edges; for (int i = 0; i < M; i ++) edges.push_back({A[i], B[i]}); for (int i = 0; i < N; i ++) { for (int bit = 0; bit < maxbit; bit ++) { if ((i & (1 << bit)) > 0) edges.push_back({i, N + bit}); } } for (int i = 0; i < N; i ++) edges.push_back({N + maxbit, i}); for (int i = N + maxbit + 1; i < N + maxbit + fict; i ++) edges.push_back({N + maxbit, i}); for (int i = N + 1; i < N + maxbit; i ++) edges.push_back({i - 1, i}); InitG(N + maxbit + fict, edges.size()); int cnt = 0; for (pair < int, int > cur : edges) { MakeG(cnt ++, cur.first, cur.second); } }
#include "Boblib.h" #include <cassert> #include <cstdio> #include<bits/stdc++.h> using namespace std; const int MAXN = 2e3 + 10; struct edge { int v, u; edge(int _v = 0, int _u = 0) { v = _v; u = _u; } }edges[MAXN * MAXN]; int deg[MAXN], non_bin[MAXN]; vector < int > adj[MAXN]; int value[MAXN], ridx[MAXN]; vector < int > path; void dfs(int v, int p) { path.push_back(v); for (int u : adj[v]) { if (u == p) continue; dfs(u, v); } } const int MAXBIT = 11; const int FICT = 15; void Bob( int V, int U, int C[], int D[] ) { if (V == 1 && U == 0) { InitMap(1, 0); return; } for (int i = 0; i < U; i ++) { edges[i] = edge(C[i], D[i]); deg[C[i]] ++; deg[D[i]] ++; } int mx = 0; for (int i = 0; i < V; i ++) if (deg[i] > deg[mx]) mx = i; for (int i = 0; i < U; i ++) { if (C[i] == mx) non_bin[D[i]] = 1; else if (D[i] == mx) non_bin[C[i]] = 1; } for (int i = 0; i < U; i ++) { if (non_bin[C[i]] || non_bin[D[i]]) continue; adj[C[i]].push_back(D[i]); adj[D[i]].push_back(C[i]); } int ver = 0; for (int i = 0; i < V; i ++) { if (non_bin[i] == 0 && deg[i] == 1) ver = i; } dfs(ver, - 1); reverse(path.begin(), path.end()); for (int i = 0; i < V; i ++) adj[i].clear(); for (int i = 0; i < U; i ++) { adj[C[i]].push_back(D[i]); adj[D[i]].push_back(C[i]); } for (int i = 0; i < path.size(); i ++) { value[path[i]] = (1 << i); } vector < pair < int, int > > ls; for (int i = 0; i < V; i ++) { for (int u : adj[i]) { if (non_bin[u] == 0) ridx[i] += value[u]; } } for (int i = 0; i < U; i ++) { if (C[i] == ver || D[i] == ver) continue; if (non_bin[C[i]] == 0 || non_bin[D[i]] == 0) continue; ls.push_back({ridx[C[i]], ridx[D[i]]}); } InitMap(V - FICT - MAXBIT, ls.size()); for (pair < int, int > cur : ls) MakeMap(cur.first, cur.second); }

Compilation message (stderr)

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