oj.uz

Submission #967081

# Submission time Handle Problem Language Result Execution time Memory
967081 2024-04-21T05:52:26 Z fcmalkcin Swapping Cities (APIO20_swap) C++17
0 / 100
 79 ms 17148 KB 
#include "swap.h"
 
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
#define pii pair<int,int>
#define fs first
#define sc second
 
const int mxn = 2e5+10;
 
vector<int> v;
int N,M;
vector<pair<int,pii>> edges;
 
void init(int NN, int MM,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	N = NN,M = MM;
	for(int i = 0;i<M;i++){
		edges.push_back(make_pair(W[i],pii(U[i],V[i])));
	}
	sort(edges.begin(),edges.end());
	return;
}
 
namespace BIS{
	vector<int> paths[mxn];
	int dp[mxn];
	queue<int> q;
	int deg[mxn];
 
	void bfs(int s,int t,int tag){
		q.push(s);
		dp[s] |= tag;
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			if(now == t)continue;
			for(auto nxt:paths[now]){
				if(dp[nxt]&tag)continue;
				dp[nxt]|=tag;
				q.push(nxt);
			}
		}
		return;
	}
 
	int cnt[mxn];
	bool check(int id,int s,int t){
		memset(dp,0,sizeof(dp));
		memset(deg,0,sizeof(deg));
		memset(cnt,0,sizeof(cnt));
		for(int i = 0;i<N;i++)paths[i].clear();
		for(int i = 0;i<=min(M-1,id);i++){
			paths[edges[i].sc.fs].push_back(edges[i].sc.sc);
			paths[edges[i].sc.sc].push_back(edges[i].sc.fs);
		}
		bfs(s,N,1);
		if(!dp[t])return false;
		for(int i = 0;i<N;i++){
			if(dp[i]){
				for(auto nxt:paths[i])deg[nxt]++;
			}
		}
		for(int i = 0;i<N;i++){
			if(deg[i])cnt[deg[i]]++;
		}
		if(*max_element(cnt+3,cnt+mxn) == 0&&cnt[1] == 2)return false;
		return true;
	}
}
 
int getMinimumFuelCapacity(int X, int Y) {
	return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 28 ms 12300 KB Output is correct
10 Correct 32 ms 13068 KB Output is correct
11 Correct 31 ms 13008 KB Output is correct
12 Correct 33 ms 13200 KB Output is correct
13 Correct 33 ms 13260 KB Output is correct
14 Correct 30 ms 12756 KB Output is correct
15 Correct 79 ms 17148 KB Output is correct
16 Correct 73 ms 17000 KB Output is correct
17 Correct 75 ms 17104 KB Output is correct
18 Correct 78 ms 17104 KB Output is correct
19 Incorrect 41 ms 12304 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Incorrect 70 ms 16288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Incorrect 2 ms 7256 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 28 ms 12300 KB Output is correct
10 Correct 32 ms 13068 KB Output is correct
11 Correct 31 ms 13008 KB Output is correct
12 Correct 33 ms 13200 KB Output is correct
13 Correct 33 ms 13260 KB Output is correct
14 Correct 30 ms 12756 KB Output is correct
15 Correct 79 ms 17148 KB Output is correct
16 Correct 73 ms 17000 KB Output is correct
17 Correct 75 ms 17104 KB Output is correct
18 Correct 78 ms 17104 KB Output is correct
19 Incorrect 70 ms 16288 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7256 KB Output isn't correct
2 Halted 0 ms 0 KB -