oj.uz

답안 #965734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
965734 2024-04-19T06:28:40 Z willychan 자매 도시 (APIO20_swap) C++17
17 / 100
 2000 ms 10520 KB 
#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
	int a;
	int b;
	int w;
};
vector<edge> es;
int n;
int m;
vector<vector<int> > side;
vector<bool> vis;
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	m = M;
	vis.resize(n,0);
	side.resize(n);
	for(int i=0;i<M;i++){
		es.push_back({U[i],V[i],W[i]});
	}
	sort(es.begin(),es.end(),[](const edge &x,const edge &y){return x.w<y.w;});
}
bool dfs(int cur,int p){
	vis[cur]=1;
	bool k=0;
	for(auto i : side[cur])	{
		int v = es[i].a+es[i].b-cur;
		if(vis[v] && v!=p) k=1;
		if(!vis[v]) if(dfs(v,cur)) k=1;
	}
	return k;
}



int check(int x,int y){
	fill(vis.begin(),vis.end(),0);
	bool cir = dfs(x,-1);
	if(!vis[y]) return 0;
	if(cir) return 1;
	int maxn = 0;
	for(int i=0;i<n;i++) if(vis[i]) maxn=max((int)side[i].size(),maxn);
	return maxn>2;
}

int getMinimumFuelCapacity(int X, int Y) {
  for(int i=0;i<n;i++) side[i].clear();
  for(int i=0;i<m;i++){
  	side[es[i].a].push_back(i);
  	side[es[i].b].push_back(i);
	if(check(X,Y)) return es[i].w;
  }
  return -1;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 14 ms 600 KB Output is correct
9 Execution timed out 2058 ms 6616 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2095 ms 10520 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 14 ms 600 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 4 ms 536 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 4 ms 348 KB Output is correct
16 Correct 5 ms 760 KB Output is correct
17 Correct 11 ms 348 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 3 ms 348 KB Output is correct
20 Correct 4 ms 572 KB Output is correct
21 Correct 6 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 4 ms 348 KB Output is correct
24 Correct 5 ms 344 KB Output is correct
25 Correct 7 ms 588 KB Output is correct
26 Correct 5 ms 604 KB Output is correct
27 Correct 10 ms 348 KB Output is correct
28 Correct 4 ms 600 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 14 ms 600 KB Output is correct
10 Execution timed out 2058 ms 6616 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 14 ms 600 KB Output is correct
9 Execution timed out 2058 ms 6616 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 14 ms 600 KB Output is correct
10 Execution timed out 2058 ms 6616 KB Time limit exceeded
11 Halted 0 ms 0 KB -