oj.uz

Submission #150078

# Submission time Handle Problem Language Result Execution time Memory
150078 2019-09-01T07:40:53 Z CHT를 사랑하는 모임(#3587, moonrabbit2, Retro3014, gs18115) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 60732 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;
	if(gp[a].size()>gp[b].size()) swap(a,b);
	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 749 ms 60216 KB Output is correct
2 Correct 664 ms 60220 KB Output is correct
3 Correct 615 ms 60344 KB Output is correct
4 Correct 615 ms 60732 KB Output is correct
5 Correct 706 ms 60472 KB Output is correct
6 Correct 610 ms 60476 KB Output is correct
7 Correct 591 ms 60220 KB Output is correct
8 Correct 716 ms 60344 KB Output is correct
9 Correct 563 ms 60216 KB Output is correct
10 Correct 638 ms 60476 KB Output is correct

Subtask #2
0 / 39.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28544 KB Output is correct
2 Correct 24 ms 28544 KB Output is correct
3 Correct 749 ms 60216 KB Output is correct
4 Correct 664 ms 60220 KB Output is correct
5 Correct 615 ms 60344 KB Output is correct
6 Correct 615 ms 60732 KB Output is correct
7 Correct 706 ms 60472 KB Output is correct
8 Correct 610 ms 60476 KB Output is correct
9 Correct 591 ms 60220 KB Output is correct
10 Correct 716 ms 60344 KB Output is correct
11 Correct 563 ms 60216 KB Output is correct
12 Correct 638 ms 60476 KB Output is correct
13 Execution timed out 5102 ms 46308 KB Time limit exceeded
14 Halted 0 ms 0 KB -