Submission #991845

#TimeUsernameProblemLanguageResultExecution timeMemory
991845danikoynovAirline Route Map (JOI18_airline)C++14
37 / 100
404 ms109432 KiB
#include "Alicelib.h" #include <cassert> #include <cstdio> #include<bits/stdc++.h> using namespace std; const int maxn = 2e3 + 10; const int maxbit = 10; const int fict = 2; /** 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 + maxbit; i ++) edges.push_back({N + maxbit, i}); for (int i = 0; i < N; i ++) { edges.push_back({N + maxbit + 1, 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 = 10; const int FICT = 2; int tf[MAXN]; 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]] ++; //cout << C[i] << " " << D[i] << endl; } ///exit(0); 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) tf[D[i]] = 1; else if (D[i] == mx) tf[C[i]] = 1; } tf[mx] = 1; int fx = 0; while(tf[fx] == 1) fx ++; non_bin[mx] = 1; non_bin[fx] = 1; for (int i = 0; i < U; i ++) { if (C[i] == fx) non_bin[D[i]] = 1; else if (D[i] == fx) non_bin[C[i]] = 1; } int cnt = 0; for (int i = 0; i < U; i ++) { if (non_bin[C[i]] || non_bin[D[i]] || C[i] == fx || C[i] == mx || D[i] == fx || D[i] == mx) continue; adj[C[i]].push_back(D[i]); adj[D[i]].push_back(C[i]); cnt ++; } assert(cnt == MAXBIT - 1); int ver = -1; for (int i = 0; i < V; i ++) { ///cout << "non bin " << i << " : " << non_bin[i] << " " << deg[i] << endl; if (non_bin[i] == 0 && adj[i].size() == 1) ver = i; } ///assert(ver != -1); ///cout << "ver " << ver << endl; dfs(ver, - 1); ///reverse(path.begin(), path.end()); //for (int p : path) // cout << p << " "; // cout << endl; 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]); }vector < pair < int, int > > ls; for (int i = 0; i < path.size(); i ++) { value[path[i]] = (1 << i); } int N = V - MAXBIT - FICT; for (int i = 0; i < V; i ++) { for (int u : adj[i]) { if (non_bin[u] == 0) ridx[i] += value[u]; } } bool sw = false; for (int i = 0; i < V; i ++) { if (non_bin[i] == 0 || i == mx || i == fx) continue; if (ridx[i] >= N) sw = true; } if (sw) { reverse(path.begin(), path.end()); for (int i = 0; i < path.size(); i ++) { value[path[i]] = (1 << i); } for (int i = 0; i < V; i ++) ridx[i] = 0; 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] == mx || D[i] == mx) continue; if (C[i] == fx || D[i] == fx) continue; if (non_bin[C[i]] == 0 || non_bin[D[i]] == 0) continue; ls.push_back({ridx[C[i]], ridx[D[i]]}); ///cout << "edge " << ls.back().first << " " << ls.back().second << endl; } 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:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for (int i = 0; i < path.size(); i ++)
      |                     ~~^~~~~~~~~~~~~
Bob.cpp:152:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 | for (int i = 0; i < path.size(); i ++)
      |                 ~~^~~~~~~~~~~~~
Bob.cpp:172:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  172 |         if (C[i] == mx || D[i] == mx)
      |         ^~
Bob.cpp:174:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  174 |             if (C[i] == fx || D[i] == fx)
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...