oj.uz

Submission #201989

# Submission time Handle Problem Language Result Execution time Memory
201989 2020-02-13T01:59:10 Z Segtree Collapse (JOI18_collapse) C++14
0 / 100
 75 ms 4432 KB 
#include<bits/stdc++.h>
#include"collapse.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(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
int n,m,q;
vector<ll> 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){
    n=N,m=t.size(),q=w.size();
    rep(i,m)if(x[i]>y[i])swap(x[i],y[i]);
    vi fans;
    rep(k,q){
	rep(i,n)g[i].clear();
	unordered_set<ll> S;
	for(int i=w[k];i>=0;i--){
	    if(S.find(x[i]*5010+y[i])==S.end()){
		if(t[k]==0&&not(x[i]<=p[k]&&p[k]+1<=y[i])){
		    g[x[i]].push_back(y[i]);
		    g[y[i]].push_back(x[i]);
		}
		S.insert(x[i]*5010+y[i]);
	    }
	}
	rep(i,n)vis[i]=0;
	ll ans=0;
	rep(i,n)if(!vis[i]){
	    ans++;
	    dfs(i);
	}
	fans.push_back(ans);
    }
    return fans;
}
/*int main(){
    
}*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 632 KB Output is correct
2 Incorrect 8 ms 636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 4344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 4432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 632 KB Output is correct
2 Incorrect 8 ms 636 KB Output isn't correct
3 Halted 0 ms 0 KB -