제출 #292063

#제출 시각아이디문제언어결과실행 시간메모리
292063AbdelrahmanBosses (BOI16_bosses)C++17
0 / 100
1 ms512 KiB
#include <bits/stdc++.h> #define endl '\n' #define modulo 1000000007 #define int long long #pragma GCC optimize("-Ofast") #define float double #define PI 3.141592653589793238462643383279502884 #define sinDegrees(x) sin((x) * PI / 180.0) #define tanDegrees(x) tan((x) * PI / 180.0) #define atanDegrees(x) atan(x)* 180.0 / PI using namespace std; unordered_map<int, vector<int> > mp; vector<pair<int, int> >vs; unordered_map<int, int>empInd; bool visited[5001] = {0}, touched[5001]={0}; int finale = 0, done=0; bool compare(pair<int, int> a, pair<int, int> b) { if (a.first!=b.first) { return a.first>b.first; } else { return a.second<b.second; } } int solve(int emp) { if (visited[emp]) return 0; visited[emp] = 1; done++; touched[emp] = 1; int current = 0; vector<pair<int, int> > myEmp; for (int i=0;i<mp[emp].size();i++) { int mpNum=mp[emp][i]; if (touched[mpNum]) { continue; } touched[mpNum] = 1; myEmp.push_back({empInd[mpNum], mpNum}); } if (myEmp.size()==0) { finale+=1; return 1; } sort(myEmp.begin(), myEmp.end(), compare); for (int i=0;i<mp[emp].size();i++) { current+=solve(myEmp[i].second); } finale+=current+1; return current+1; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for (int i=0;i<n;i++) { int a; cin>>a; while (a--) { int b; cin>>b; mp[b-1].push_back(i); } } for (int i=0;i<n;i++) { vs.push_back({mp[i].size(), i}); } sort(vs.begin(), vs.end(), compare); for (int i=0;i<n;i++) { empInd[vs[i].second] = vs[i].first; } int mini=INT_MAX; for (int i=0;i<n;i++) { solve(vs[i].second); if (done==n) { mini = min(finale, mini); } memset(visited, 0, sizeof(visited)); memset(touched, 0, sizeof(touched)); finale = 0; done=0; } cout<<mini; }

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

bosses.cpp: In function 'long long int solve(long long int)':
bosses.cpp:41:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i=0;i<mp[emp].size();i++)
      |                  ~^~~~~~~~~~~~~~~
bosses.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i=0;i<mp[emp].size();i++)
      |                  ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...