| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1035414 |
2024-07-26T10:35:17 Z |
vjudge1 |
Simurgh (IOI17_simurgh) |
C++17 |
|
765 ms |
1048576 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
#define Z 510
using namespace std;
vector<int>R;
int N_,K_;
int indexofr[Z][Z],deg[Z],royaltree[Z],parind[Z],acpar[Z],dep[Z];
vector<pair<int,int>>tre;
vector<int>U,V;
vector<int>AADJ[Z],bak[Z];
bitset<Z>vis,col,don;
void assert2(int k){
if(!k){
vector<int>v;
for(int i=0;;i++)
v.push_back(i);
}
}
void AD(int x,int y){
R.push_back(indexofr[x][y]-1);
}
int Q(){
return count_common_roads(R);
}
int Q(vector<int>v){
for(auto&i:v)i--;
return count_common_roads(v);
}
struct dsu{
int par[501];
int abp(int n){
return par[n]?par[n]=abp(par[n]):n;
}
bool merge(int a,int b){
a=abp(a+1),b=abp(b+1);
if(a==b) return 0;
return par[a]=b;
}
void reset(){
memset(par,0,sizeof par);
}
} tis, TIS2;
vector<int>path{-1};
void calcfortree(int n){
path.push_back(n);
for(auto i:AADJ[n])
if(parind[i]==n)
calcfortree(i);
int d=1e9;
for(auto i:AADJ[n])
d=min(d,dep[i]);
if(d<dep[n]-1){
vector<int>V;
int D=indexofr[n][path[d]];
for(auto[x,y]:tre)
V.push_back(indexofr[x][y]);
V.push_back(D);
vector<int>undet,det,path2=path;
path.pop_back();
while(path2.size()>d+1) {
if(don[parind[path2.back()]])
det.push_back(path2.back());
else undet.push_back(path2.back()),
col[parind[path2.back()]]=0;
don[parind[path2.back()]]=1;path2.pop_back();
}
if(undet.empty()) return;
if(det.empty()){
map<int,vector<int>>mp;
for(auto i:undet) {
int RD=indexofr[i][acpar[i]];
V.erase(find(V.begin(),V.end(),RD));
mp[Q(V)].push_back(i);
V.push_back(RD);
}
V.erase(find(V.begin(),V.end(),D));
mp[Q(V)].push_back(N_);
V.push_back(D);
if(mp.size()==2)
for(auto i:mp[mp.begin()->first])
if(i<N_) col[parind[i]]=1;
} else {
int rk=det[0];
int RD=indexofr[rk][acpar[rk]];
V.erase(find(V.begin(),V.end(),RD));
int akt=Q(V)+col[parind[rk]];
V.push_back(RD);
for(auto i:undet){
RD=indexofr[i][acpar[i]];
V.erase(find(V.begin(),V.end(),RD));
col[parind[i]]=akt!=Q(V);
V.push_back(RD);
}
}
} else path.pop_back();
}
void gendfstree(int n,int p){
vis[n]=1,dep[n]=dep[p]+1;
for(auto i:AADJ[n]){
if(i==p)continue;
if(!vis[i]) acpar[i]=n,
parind[i]=tre.size(),
tre.push_back({n,i}),
gendfstree(i,n);
}
if(!n)calcfortree(n);
}
vector<int>ans;
int countst(vector<int> x,int pivot){
R.clear();
tis.reset();
for(auto i:x)AD(pivot,i),
tis.merge(pivot,i);
int K=0;
for(auto[X,Y]:tre)
if(tis.merge(X,Y))
AD(X,Y),K-=col[parind[Y]];
return K+Q();
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
for(int i=0;i<n;i++)
col[i]=1;
U=u;
V=v;
N_=n;
int m=u.size();
for(int i=0;i<m;i++)
AADJ[u[i]].push_back(v[i]),
AADJ[v[i]].push_back(u[i]),
indexofr[u[i]][v[i]]=indexofr[v[i]][u[i]]=i+1;
gendfstree(0,0);
for(auto[X,Y]:tre)
AD(X,Y);
assert2(Q()==col.count()-1);
for(int i=1;i<n;i++)
cerr<<"edge from "<<acpar[i]<<" to "<<i<<" has color "<<col[parind[i]]<<'\n';
for(int i=0;i<n;i++){
vector<int>v;
for(int j=0;j<n;j++)
if(indexofr[i][j])
v.push_back(j);
deg[i]=countst(v,i);
}
set<int>st;
for(int i=0;i<n;i++)
st.insert(i);
vector<int>done;
for(int i=1;i<n;i++){
int x=0;
for(int i=0;i<n;i++)
if(deg[i]==1)x=i;
R.clear();
deg[x]=0;
st.erase(x);
vector<int>V;
for(auto i:st)
if(indexofr[i][x])
V.push_back(i);
while(V.size()>1){
vector<int>a[2];
for(int i=0;i<V.size();i++)
a[i%2].push_back(V[i]);
V=a[countst(a[1],x)];
}
deg[V[0]]--;
ans.push_back(indexofr[x][V[0]]-1);
}
R=ans;
//assert(Q()==n-1);
return ans;
}
Compilation message
simurgh.cpp: In member function 'bool dsu::merge(int, int)':
simurgh.cpp:37:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
37 | return par[a]=b;
| ~~~~~~^~
simurgh.cpp: In function 'void calcfortree(int)':
simurgh.cpp:60:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
60 | while(path2.size()>d+1) {
| ~~~~~~~~~~~~^~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:135:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
135 | assert2(Q()==col.count()-1);
| ~~~^~~~~~~~~~~~~~~
simurgh.cpp:162:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for(int i=0;i<V.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
472 KB |
correct |
| 2 |
Runtime error |
709 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
472 KB |
correct |
| 2 |
Runtime error |
709 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
472 KB |
correct |
| 2 |
Runtime error |
709 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
correct |
| 2 |
Runtime error |
765 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
472 KB |
correct |
| 2 |
Runtime error |
709 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
