| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 608897 |
2022-07-27T11:04:12 Z |
jk410 |
Keys (IOI21_keys) |
C++17 |
|
3000 ms |
197888 KB |
//koosaga is god and I'm invincible
//upsolving
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define sz(v) ((int)(v).size())
using namespace std;
const int INF=(int)1e9;
struct dsjs{
vector<int> par;
void init(int n){
par.resize(n);
for (int i=0; i<n; i++)
par[i]=i;
}
int get_par(int v){
if (v==par[v])
return v;
return par[v]=get_par(par[v]);
}
bool my_merge(int a,int b){
a=get_par(a);
b=get_par(b);
if (a==b)
return false;
par[b]=a;
return true;
}
};
vector<stack<int>> psb_edge;
vector<multiset<pair<int,int>>> impsb_edge;
vector<set<int>> key;
vector<int> nxt;
dsjs idx,graph;
void merge_vertex(int cur,int to){
if (sz(psb_edge[cur])>sz(psb_edge[to]))
swap(psb_edge[cur],psb_edge[to]);
while (!psb_edge[cur].empty()){
psb_edge[to].push(psb_edge[cur].top());
psb_edge[cur].pop();
}
if (sz(impsb_edge[cur])<sz(impsb_edge[to]))
swap(impsb_edge[cur],impsb_edge[to]);
for (auto i=impsb_edge[cur].begin(); i!=impsb_edge[cur].end(); i=impsb_edge[cur].erase(i))
impsb_edge[to].insert(*i);
if (sz(key[cur])>sz(key[to]))
swap(key[cur],key[to]);
for (auto i=key[cur].begin(); i!=key[cur].end(); i=key[cur].erase(i))
key[to].insert(*i);
for (int i:key[to]){
auto it=impsb_edge[to].lower_bound({i,-1});
while (it!=impsb_edge[to].end()&&it->first==i){
psb_edge[to].push(it->second);
it=impsb_edge[to].erase(it);
}
}
}
vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
int n=sz(r);
int m=sz(c);
psb_edge.resize(n*2);
impsb_edge.resize(n*2);
nxt.resize(n*2);
key.resize(n*2);
idx.init(n*2);
graph.init(n*2);
vector<int> ret(n);
for (int i=0; i<m; i++){
if (c[i]==r[u[i]])
psb_edge[u[i]].push(v[i]);
else
impsb_edge[u[i]].insert({c[i],v[i]});
if (c[i]==r[v[i]])
psb_edge[v[i]].push(u[i]);
else
impsb_edge[v[i]].insert({c[i],u[i]});
}
for (int i=0; i<n; i++){
key[i].insert(r[i]);
nxt[i]=i;
if (!psb_edge[i].empty()){
nxt[i]=psb_edge[i].top();
psb_edge[i].pop();
}
}
for (int i=0; i<n; i++){
//cout<<i<<" "<<nxt[i]<<" "<<idx.get_par(i)<<" "<<idx.get_par(nxt[i])<<"\n";
if (idx.get_par(i)==idx.get_par(nxt[i]))
continue;
if (!graph.my_merge(idx.get_par(i),idx.get_par(nxt[i]))){
//cout<<"!"<<idx.get_par(i)<<" "<<graph.get_par(idx.get_par(i))<<"\n";
graph.par[graph.get_par(idx.get_par(i))]=n;
for (int j=idx.get_par(i);;){
merge_vertex(j,n);
int tmp=j;
j=idx.get_par(nxt[j]);
idx.par[idx.get_par(tmp)]=n;
if (j==idx.get_par(i))
break;
}
nxt[n]=n;
while (!psb_edge[n].empty()&&idx.get_par(psb_edge[n].top())==n){
//cout<<psb_edge[n].top()<<" "<<idx.get_par(psb_edge[n].top())<<"\n";
psb_edge[n].pop();
}
if (!psb_edge[n].empty()){
nxt[n]=psb_edge[n].top();
psb_edge[n].pop();
}
//cout<<n<<" "<<nxt[n]<<" "<<idx.get_par(nxt[n])<<"\n";
n++;
}
}
vector<int> cnt(n);
for (int i=0; i<sz(ret); i++)
cnt[idx.get_par(i)]++;
for (int i=0; i<sz(ret); i++){
ret[i]=INF;
if (idx.get_par(i)==idx.get_par(nxt[i]))
ret[i]=cnt[idx.get_par(i)];
//cout<<i<<" "<<idx.get_par(i)<<" "<<idx.get_par(nxt[i])<<" "<<ret[i]<<"\n";
}
//cout<<"\n";
int minv=*min_element(all(ret));
for (int i=0; i<sz(ret); i++)
ret[i]=(ret[i]==minv);
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
432 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
432 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| 11 |
Correct |
1 ms |
552 KB |
Output is correct |
| 12 |
Correct |
1 ms |
556 KB |
Output is correct |
| 13 |
Correct |
0 ms |
300 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
432 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| 11 |
Correct |
1 ms |
552 KB |
Output is correct |
| 12 |
Correct |
1 ms |
556 KB |
Output is correct |
| 13 |
Correct |
0 ms |
300 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
432 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Execution timed out |
3062 ms |
197888 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
296 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
304 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
432 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| 11 |
Correct |
1 ms |
552 KB |
Output is correct |
| 12 |
Correct |
1 ms |
556 KB |
Output is correct |
| 13 |
Correct |
0 ms |
300 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
