oj.uz

답안 #405893

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405893 2021-05-17T03:06:43 Z amunduzbaev 자매 도시 (APIO20_swap) C++14
0 / 100
 2000 ms 224296 KB 
#include "swap.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define int long long

const int NN = 1e5+5;
int sub, used[NN], found, pos[NN], is[NN];
vector<int> pref[NN];
vector<pair<int, int>> edges[NN];
vector<pair<int, int>> ss;

void dfs(int u, int p = -1){
	if(used[u]){ found = 1; return; } 
	used[u] = 1;
	//cout<<u<<" ";
	for(auto x : edges[u]) { 
		if(x.ff == p) continue;
		ss.pb({u, x.ss});
		dfs(x.ff, u);
	}
}

void init(int32_t N, int32_t M,
	vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
	//cout<<"\n";
	for(int i=0;i<M;i++){
		edges[U[i]].pb({V[i], W[i]});
		edges[V[i]].pb({U[i], W[i]});
	}
	if(M == N) sub = 1;
	else sub = 2;
	int last = 0;
	for(int i=0;i<N;i++){
		if(used[i]) continue;
		ss.clear(), found = 0;
		dfs(i);
		//cout<<"\n";
		if(found){
			pref[last].pb(0);
			ss.pop_back();
			for(int j=0;j<sz(ss);j++){
				is[ss[j].ff] = last+1;
				pos[ss[j].ff] = j+1;
				pref[last].pb(ss[j].ss);
			} for(int j=1;j<=sz(ss);j++) pref[last][j] += pref[last][j-1];
			last++;
		}
	} 
}

/*

5 5
1 0 1
2 1 2
3 2 3
4 3 4
4 0 5
5
0 1
1 2
2 3
3 4
4 0

*/

int32_t getMinimumFuelCapacity(int32_t x, int32_t y) {
	if(x > y) swap(x, y);
	if(sub == 1){
		if(is[x] != is[y] || !is[x]) return -1;
		int l = is[x] - 1;
		int i = pos[x], j = pos[y];
		if(i > j) swap(i, j);
		for(auto x : pref[l]) cout<<x<<" ";
		//cout<<"\n";
		//cout<<i<<" "<<j<<"\n";
		return max(pref[l][j-1] - pref[l][i-1], pref[l][i-1] + pref[l][sz(pref[l])-1] - pref[l][j-1]);
	} return -1;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 84 ms 18968 KB Output is correct
10 Correct 85 ms 22888 KB Output is correct
11 Correct 84 ms 21980 KB Output is correct
12 Correct 85 ms 23276 KB Output is correct
13 Correct 95 ms 25784 KB Output is correct
14 Correct 88 ms 18072 KB Output is correct
15 Correct 146 ms 24312 KB Output is correct
16 Correct 142 ms 22084 KB Output is correct
17 Correct 153 ms 27384 KB Output is correct
18 Correct 181 ms 25500 KB Output is correct
19 Execution timed out 2074 ms 224296 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Incorrect 112 ms 16976 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Incorrect 4 ms 4940 KB Output isn't correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 84 ms 18968 KB Output is correct
10 Correct 85 ms 22888 KB Output is correct
11 Correct 84 ms 21980 KB Output is correct
12 Correct 85 ms 23276 KB Output is correct
13 Correct 95 ms 25784 KB Output is correct
14 Correct 88 ms 18072 KB Output is correct
15 Correct 146 ms 24312 KB Output is correct
16 Correct 142 ms 22084 KB Output is correct
17 Correct 153 ms 27384 KB Output is correct
18 Correct 181 ms 25500 KB Output is correct
19 Incorrect 112 ms 16976 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct