oj.uz

Submission #207104

# Submission time Handle Problem Language Result Execution time Memory
207104 2020-03-06T13:21:29 Z Segtree Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 6136 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_set>
#include"collapse.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
//namespace solver1{
	vi g[5010];
	bool vis[5010];
	void dfs(ll x){
		if(vis[x])return ;
		vis[x]=1;
		for(auto y:g[x])dfs(y);
	}
	vi simulateCollapse(int N,vi T,vi X,vi Y,vi W,vi P){
		int C=T.size(),Q=W.size();
		for(int i=0;i<C;i++){
			if(X[i]>Y[i])swap(X[i],Y[i]);
		}
		vi FANS(Q);
		for(int i=0;i<Q;i++){
			for(int j=0;j<N;j++){
				g[j].clear();
				vis[j]=0;
			}
			unordered_set<ll> S;
			for(int j=0;j<=W[i];j++){
				ll key=X[j]*5010+Y[j];
				if(S.count(key))S.erase(key);
				else S.insert(key);
			}
			for(auto key:S){
				ll x=key/5010,y=key%5010;
				if(not(x<=P[i]&&P[i]+1<=y)){
					g[x].push_back(y);
					g[y].push_back(x);
				}
			}
			
			ll cnt=0;
			for(int j=0;j<N;j++){
				if(vis[j])continue;
				dfs(j);
				cnt++;
			}
			FANS[i]=cnt;
		}
		return FANS;
	}
//};
/*int main(){
	ll N,C,Q;
	cin>>N>>C>>Q;
	vi T(C),X(C),Y(C),W(Q),P(Q);
	rep(i,C){
		cin>>T[i]>>X[i]>>Y[i];
	}
	rep(i,Q){
		cin>>W[i]>>P[i];
	}
	vi ANS1=solver1::simulateCollapse(N,T,X,Y,W,P);
	for(auto t:ANS1)cout<<t<<endl;
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 768 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 14 ms 504 KB Output is correct
4 Correct 21 ms 504 KB Output is correct
5 Correct 657 ms 900 KB Output is correct
6 Correct 1516 ms 1076 KB Output is correct
7 Correct 145 ms 632 KB Output is correct
8 Correct 144 ms 632 KB Output is correct
9 Correct 878 ms 1016 KB Output is correct
10 Correct 1316 ms 992 KB Output is correct
11 Correct 2102 ms 1248 KB Output is correct
12 Correct 2093 ms 1276 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2808 KB Output is correct
2 Correct 77 ms 2808 KB Output is correct
3 Execution timed out 15087 ms 6136 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2808 KB Output is correct
2 Correct 85 ms 2812 KB Output is correct
3 Correct 147 ms 2808 KB Output is correct
4 Correct 262 ms 2936 KB Output is correct
5 Correct 3303 ms 3192 KB Output is correct
6 Execution timed out 15074 ms 3576 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 768 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 14 ms 504 KB Output is correct
4 Correct 21 ms 504 KB Output is correct
5 Correct 657 ms 900 KB Output is correct
6 Correct 1516 ms 1076 KB Output is correct
7 Correct 145 ms 632 KB Output is correct
8 Correct 144 ms 632 KB Output is correct
9 Correct 878 ms 1016 KB Output is correct
10 Correct 1316 ms 992 KB Output is correct
11 Correct 2102 ms 1248 KB Output is correct
12 Correct 2093 ms 1276 KB Output is correct
13 Correct 51 ms 2808 KB Output is correct
14 Correct 77 ms 2808 KB Output is correct
15 Execution timed out 15087 ms 6136 KB Time limit exceeded
16 Halted 0 ms 0 KB -