# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
369627 |
2021-02-22T06:28:07 Z |
YJU |
Collapse (JOI18_collapse) |
C++14 |
|
15000 ms |
5868 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=4e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll n,q,c,dir[N];
set<pll> ms;
ll f(ll id){
return (id==dir[id]?id:dir[id]=f(dir[id]));
}
vector<ll> simulateCollapse(ll _N,vector<ll> ty,vector<ll> x,vector<ll> y,vector<ll> w,vector<ll> p){
n=_N;q=SZ(w);c=SZ(ty);
vector<ll> ret;
REP(i,c){
++x[i];++y[i];
if(x[i]>y[i])swap(x[i],y[i]);
}
REP(i,q)++p[i];
REP(i,q){
ms.clear();
REP(j,w[i]+1){
if(ty[j]==0){
ms.insert(mp(x[j],y[j]));
}else{
ms.erase(mp(x[j],y[j]));
}
}
ll cnt=n;
REP1(j,n)dir[j]=j;
for(auto j:ms){
if(p[i]<j.X||p[i]>=j.Y){
if(f(j.X)==f(j.Y))continue;
--cnt;
dir[f(j.X)]=f(j.Y);
}
}
ret.pb(cnt);
}
return ret;
}
/*
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
vector<ll> T={0,0,0,0};
vector<ll> TX={0,1,2,4};
vector<ll> TY={1,3,4,0};
vector<ll> W={3};
vector<ll> P={1};
vector<ll> ans=simulateCollapse(5,T,TX,TY,W,P);
for(auto i:ans)cout<<i<<"\n";
return 0;
}
*/
Compilation message
collapse.cpp:11:18: warning: overflow in conversion from 'long long int' to 'll' {aka 'int'} changes value from '1152921504606846976' to '0' [-Woverflow]
11 | const ll INF=(1LL<<60);
| ~~~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
187 ms |
620 KB |
Output is correct |
2 |
Correct |
3 ms |
492 KB |
Output is correct |
3 |
Correct |
7 ms |
492 KB |
Output is correct |
4 |
Correct |
13 ms |
492 KB |
Output is correct |
5 |
Correct |
995 ms |
1004 KB |
Output is correct |
6 |
Correct |
2480 ms |
1132 KB |
Output is correct |
7 |
Correct |
15 ms |
492 KB |
Output is correct |
8 |
Correct |
16 ms |
492 KB |
Output is correct |
9 |
Correct |
944 ms |
828 KB |
Output is correct |
10 |
Correct |
1684 ms |
880 KB |
Output is correct |
11 |
Correct |
2550 ms |
1132 KB |
Output is correct |
12 |
Correct |
2712 ms |
1288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
2536 KB |
Output is correct |
2 |
Correct |
44 ms |
2536 KB |
Output is correct |
3 |
Execution timed out |
15068 ms |
5868 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
2536 KB |
Output is correct |
2 |
Correct |
48 ms |
2536 KB |
Output is correct |
3 |
Correct |
93 ms |
2536 KB |
Output is correct |
4 |
Correct |
207 ms |
2592 KB |
Output is correct |
5 |
Correct |
3304 ms |
2680 KB |
Output is correct |
6 |
Execution timed out |
15091 ms |
2484 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
187 ms |
620 KB |
Output is correct |
2 |
Correct |
3 ms |
492 KB |
Output is correct |
3 |
Correct |
7 ms |
492 KB |
Output is correct |
4 |
Correct |
13 ms |
492 KB |
Output is correct |
5 |
Correct |
995 ms |
1004 KB |
Output is correct |
6 |
Correct |
2480 ms |
1132 KB |
Output is correct |
7 |
Correct |
15 ms |
492 KB |
Output is correct |
8 |
Correct |
16 ms |
492 KB |
Output is correct |
9 |
Correct |
944 ms |
828 KB |
Output is correct |
10 |
Correct |
1684 ms |
880 KB |
Output is correct |
11 |
Correct |
2550 ms |
1132 KB |
Output is correct |
12 |
Correct |
2712 ms |
1288 KB |
Output is correct |
13 |
Correct |
31 ms |
2536 KB |
Output is correct |
14 |
Correct |
44 ms |
2536 KB |
Output is correct |
15 |
Execution timed out |
15068 ms |
5868 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |