oj.uz

Submission #369627

# Submission time Handle Problem Language Result Execution time Memory
369627 2021-02-22T06:28:07 Z YJU Collapse (JOI18_collapse) C++14
5 / 100
 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);
      |              ~~~~^~~~~

Subtask #1
5.0 / 5.0

# 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

Subtask #2
0 / 30.0

# 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 -

Subtask #3
0 / 30.0

# 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 -

Subtask #4
0 / 35.0

# 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 -