제출 #561925

#제출 시각아이디문제언어결과실행 시간메모리
561925timreizinMeetings (JOI19_meetings)C++17
100 / 100
653 ms920 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); void find(vector<int> &vertices) { if (vertices.size() == 1) return; if (vertices.size() == 2) { adj[vertices.front()].push_back(vertices.back()); adj[vertices.back()].push_back(vertices.front()); return; } 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]; path.push_back(x); for (int i = 0; i < vertices.size(); ++i) { if (x == vertices[i] || y == vertices[i]) continue; int r = Query(x, y, vertices[i]); if (r != vertices[i]) comps[r].push_back(vertices[i]); else path.push_back(r); } for (auto &[pivot, vertices] : comps) { vertices.push_back(pivot); find(vertices); } sort(path.begin() + 1, path.end(), [&x](int a, int b) { return Query(x, a, b) == a; }); path.push_back(y); 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]); } } void Solve(int n) { adj.resize(n); set<int> path; vector<int> vertices(n); iota(vertices.begin(), vertices.end(), 0); find(vertices); for (int i = 0; i < n; ++i) for (int u : adj[i]) if (i < u) Bridge(i, u); }

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

meetings.cpp: In function 'void find(std::vector<int>&)':
meetings.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < vertices.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~
meetings.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     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...