| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 410313 |
2021-05-22T13:31:00 Z |
Antekb |
Simurgh (IOI17_simurgh) |
C++14 |
|
1 ms |
204 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> U, V;
map<vector<int>, int> M;
int count(vector<int> v){
//cout<<v.size()<<"\n";
sort(v.begin(), v.end());
if(M.find(v)==M.end()) M[v]=count_common_roads(v);
return M[v];
}
vector<int> r;
int find(int v){
if(v==r[v])return v;
return r[v]=find(r[v]);
}
void Union(int u, int v){
r[u]=v;
}
int spe;
vector<int> V2[505];
vector<int> span(vector<int> &kol){
r.resize(n);
iota(r.begin(), r.end(), 0);
vector<int> ans;
for(int i:kol){
//cout<<U[i]<<" "<<V[i]<<"\n";
int u=find(U[i]), v=find(V[i]);
if(U[i]==spe)V2[v].push_back(i);
else if(V[i]==spe)V2[u].push_back(i);
else if(u!=v){
Union(u, v);
ans.push_back(i);
}
}
return ans;
}
vector<int> dobre;
std::vector<int> find_roads(int _n, std::vector<int> u2, std::vector<int> v2) {
U=u2;
V=v2;
n=_n;
int m=U.size();
vector<int> edg(m);
iota(edg.begin(), edg.end(), 0);
for(int i=0; i<n; i++){
int k=edg.size()-1;
for(int j=0; j<k; j++){
if(U[edg[j]]==i || V[edg[j]]==i){
while(k>=0 && (U[edg[k]]==i || V[edg[k]]==i))k--;
if(j>k)break;
swap(edg[j], edg[k]);
}
}
spe=i;
for(int j=0; j<n; j++)V2[j].clear();
vector<int> tre=span(edg);
/*bool b=1;
for(int j=0; j<tre.size()-1; j++){
if((U[tre[j]]==i || V[tre[j]]==i)){
swap(tre[j], tre.back());
}
}
for(int j=0; j<tre.size()-1; j++){
if((U[tre[j]]==i || V[tre[j]]==i)){
b=0;
}
}
if(b){*/
//cout<<i<<" a\n";
vector<int> gdzie;
for(int j=0; j<n; j++){
if(V2[j].size()){
//cout<<"b";
gdzie.push_back(j);
tre.push_back(V2[j].back());
}
}
//cout<<tre.size()<<"\n";
for(int k=0; k<gdzie.size(); k++){
vector<int> ans;
int M=0;
//cout<<tre[0]<<" "<<tre[1]<<" "<<tre[2]<<" "<<tre[3]<<" b\n";
for(int j:V2[gdzie[k]]){
//cout<<n-1-k<<"\n";
if(U[j]==i || V[j]==i){
tre[n-2-k]=j;
//cout<<tre[0]<<" "<<tre[1]<<" "<<tre[2]<<"\n";
ans.push_back(count(tre));
M=max(M, ans.back());
//cout<<j<<" "<<ans.back()<<"\n";
}
}
int cnt=0;
deque<int> todo;
for(int j:V2[gdzie[k]]){
//if(U[edg[j]]==i || V[edg[j]]==i){
if(ans[cnt]<M){
todo.push_back(j);
//cout<<todo.back()<<"q ";
}
cnt++;
//}
}
vector<int> edg2;
for(int j=0; j<edg.size(); j++){
if(todo.size() && edg[j]==todo.front()){
todo.pop_front();
}
else edg2.push_back(edg[j]);
}
edg=edg2;
//cout<<"\n";
}
}
//for(int j:edg)cout<<j<<" ";
return edg;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:81:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int k=0; k<gdzie.size(); k++){
| ~^~~~~~~~~~~~~
simurgh.cpp:107:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int j=0; j<edg.size(); j++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
