oj.uz

Submission #201990

# Submission time Handle Problem Language Result Execution time Memory
201990 2020-02-13T02:12:00 Z Segtree Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 6392 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[i]==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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 632 KB Output is correct
2 Correct 10 ms 632 KB Output is correct
3 Correct 15 ms 632 KB Output is correct
4 Correct 19 ms 504 KB Output is correct
5 Correct 130 ms 760 KB Output is correct
6 Correct 1483 ms 1016 KB Output is correct
7 Correct 129 ms 632 KB Output is correct
8 Correct 132 ms 632 KB Output is correct
9 Correct 1018 ms 888 KB Output is correct
10 Correct 1317 ms 1144 KB Output is correct
11 Correct 2143 ms 1272 KB Output is correct
12 Correct 2085 ms 1400 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2676 KB Output is correct
2 Correct 72 ms 3060 KB Output is correct
3 Execution timed out 15019 ms 6392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2676 KB Output is correct
2 Correct 89 ms 3060 KB Output is correct
3 Correct 172 ms 3060 KB Output is correct
4 Correct 314 ms 3188 KB Output is correct
5 Correct 3629 ms 3568 KB Output is correct
6 Execution timed out 15071 ms 3108 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 632 KB Output is correct
2 Correct 10 ms 632 KB Output is correct
3 Correct 15 ms 632 KB Output is correct
4 Correct 19 ms 504 KB Output is correct
5 Correct 130 ms 760 KB Output is correct
6 Correct 1483 ms 1016 KB Output is correct
7 Correct 129 ms 632 KB Output is correct
8 Correct 132 ms 632 KB Output is correct
9 Correct 1018 ms 888 KB Output is correct
10 Correct 1317 ms 1144 KB Output is correct
11 Correct 2143 ms 1272 KB Output is correct
12 Correct 2085 ms 1400 KB Output is correct
13 Correct 44 ms 2676 KB Output is correct
14 Correct 72 ms 3060 KB Output is correct
15 Execution timed out 15019 ms 6392 KB Time limit exceeded
16 Halted 0 ms 0 KB -