제출 #561922

#제출 시각아이디문제언어결과실행 시간메모리
561922timreizinMeetings (JOI19_meetings)C++17
100 / 100
647 ms872 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include "meetings.h" #include <random> #include <vector> #include <set> #include <numeric> #include <algorithm> #include <map> #include <cassert> using namespace std; vector<vector<int>> adj; mt19937 gen(555); int q = 0; int find(vector<int> vertices, int pivot, set<int> path) { if (vertices.size() == 1) return vertices.front(); if (vertices.size() == 2) { adj[vertices.front()].push_back(vertices.back()); adj[vertices.back()].push_back(vertices.front()); } else { vector<int> path; map<int, vector<int>> comps; int x = uniform_int_distribution<>(0, (int)vertices.size() - 1)(gen); int y = x; while (y == x) y = uniform_int_distribution<>(0, (int)vertices.size() - 1)(gen); x = vertices[x]; y = vertices[y]; for (int i = 0; i < vertices.size(); ++i) { if (x == vertices[i] || y == vertices[i]) continue; int r = Query(x, y, vertices[i]); ++q; if (r != vertices[i]) comps[r].push_back(vertices[i]); else path.push_back(r); } for (auto &[pivot, vertices]: comps) { /*vector<bool> used(vertices.size()); int left = vertices.size(); while (left) { int p = uniform_int_distribution<>(1, left)(gen); for (int i = 0; i < vertices.size(); ++i) { p -= !used[i]; if (!p) { --left; used[i] = true; p = vertices[i]; break; } } vector<int> next{p}; set<int> path; for (int i = 0; i < vertices.size(); ++i) { if (!used[i]) { int r = Query(vertices[i], p, pivot); ++q; if (r != pivot) { used[i] = true; --left; next.push_back(vertices[i]); if (r == vertices[i]) path.insert(r); } } } int e = find(next, p, path); adj[pivot].push_back(e); adj[e].push_back(pivot); }*/ vertices.push_back(pivot); find(vertices, pivot, set<int>()); } sort(path.begin(), path.end(), [&x](int a, int b) { return Query(x, a, b) == a; }); if (!path.empty()) { adj[x].push_back(path.front()); adj[path.front()].push_back(x); adj[y].push_back(path.back()); adj[path.back()].push_back(y); } else { adj[x].push_back(y); adj[y].push_back(x); } for (int i = 0; i + 1 < path.size(); ++i) { adj[path[i]].push_back(path[i + 1]); adj[path[i + 1]].push_back(path[i]); } } int v = pivot; while (!path.empty()) { for (int u : adj[v]) { if (path.find(u) != path.end()) { path.erase(u); v = u; } } } return v; } void Solve(int n) { adj.resize(n); set<int> path; vector<int> vertices(n); iota(vertices.begin(), vertices.end(), 0); find(vertices, 0, path); for (int i = 0; i < n; ++i) { for (int u : adj[i]) { if (i < u) Bridge(i, u); } } assert(q <= 25000); }

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In function 'int find(std::vector<int>, int, std::set<int>)':
meetings.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < vertices.size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~
meetings.cpp:99:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int i = 0; i + 1 < path.size(); ++i)
      |                         ~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...