oj.uz

Submission #150015

# Submission time Handle Problem Language Result Execution time Memory
150015 2019-09-01T07:33:24 Z CHT를 사랑하는 모임(#3587, moonrabbit2, Retro3014, gs18115) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 62140 KB 
#include "island.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int,int> TP;
typedef vector<vector<ll>> mat;
const int N=3e5+5;
const ll mod=1e9+7;
int n,m,k,a[N],u[N],v[N];
int par[N]; vector<int> g[N];
vector<int> gp[N]; // 소속되었던 그룹 번호들
map<int,int> mp[N];
int fi(int x)
{
	if(par[x]==x) return x;
	return par[x]=fi(par[x]);
}
void un(int x,int y,int t)
{
	x=fi(x); y=fi(y);
	if(g[x].size()<g[y].size()) swap(x,y);
	par[y]=x;
	for(auto &it : g[y]){
		if(mp[x][a[it]]) continue;
		gp[a[it]].push_back(x);
		g[x].push_back(it);
		//cout<<x<<" with "<<y<<" : "<<it<<" , "<<a[it]<<" , "<<x<<" , "<<t<<endl;
		mp[x][a[it]]=t;
	}
}
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	n=F.size(); m=S.size(); k=K;
	for(int i=0;i<n;i++) a[i+1]=F[i]+1;
	for(int i=0;i<m;i++) u[i+1]=S[i]+1,v[i+1]=E[i]+1;
	for(int i=1;i<=n;i++){
		par[i]=i;
		gp[a[i]].push_back(i);
		g[i].push_back(i);
		mp[i][a[i]]=m+1;
	}
	for(int i=m;i>=1;i--){
		if(fi(u[i])==fi(v[i])) continue;
		un(u[i],v[i],i);
	}
}
int Separate(int a,int b)
{
	a++; b++;
	int ans=1;
	for(auto &g : gp[a]){
		if(!mp[g][b]) continue;
		else ans=max(ans,min(mp[g][a],mp[g][b]));
	}
	return ans;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 61628 KB Output is correct
2 Correct 595 ms 61500 KB Output is correct
3 Correct 620 ms 61620 KB Output is correct
4 Correct 623 ms 62140 KB Output is correct
5 Correct 622 ms 61748 KB Output is correct
6 Correct 603 ms 61752 KB Output is correct
7 Correct 602 ms 61492 KB Output is correct
8 Correct 604 ms 61620 KB Output is correct
9 Correct 622 ms 61492 KB Output is correct
10 Correct 621 ms 61756 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28544 KB Output is correct
2 Correct 21 ms 28544 KB Output is correct
3 Execution timed out 5100 ms 47416 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28544 KB Output is correct
2 Correct 21 ms 28544 KB Output is correct
3 Correct 730 ms 61628 KB Output is correct
4 Correct 595 ms 61500 KB Output is correct
5 Correct 620 ms 61620 KB Output is correct
6 Correct 623 ms 62140 KB Output is correct
7 Correct 622 ms 61748 KB Output is correct
8 Correct 603 ms 61752 KB Output is correct
9 Correct 602 ms 61492 KB Output is correct
10 Correct 604 ms 61620 KB Output is correct
11 Correct 622 ms 61492 KB Output is correct
12 Correct 621 ms 61756 KB Output is correct
13 Execution timed out 5100 ms 47416 KB Time limit exceeded
14 Halted 0 ms 0 KB -