oj.uz

Submission #924405

# Submission time Handle Problem Language Result Execution time Memory
924405 2024-02-09T03:03:26 Z pcc City Mapping (NOI18_citymapping) C++14
32 / 100
 2 ms 604 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

#define pll pair<ll,ll>
#define fs first
#define sc second
#define ll long long
#define pii pair<int,int>
const int mxn = 1010;
vector<pair<ll,pii>> edges;
int dsu[mxn];

int root(int k){
	return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<pll> coords;
	coords.push_back(make_pair(0ll,1));
	coords.push_back(make_pair(get_distance(1,2),2));
	pll pos = make_pair(0,coords.back().fs);
	for(int i = 3;i<=N;i++){
		ll ta = get_distance(1,i),tb = get_distance(2,i);
		if(ta+tb == pos.sc-pos.fs)coords.push_back(make_pair(ta,i));
		else if(ta<tb)coords.push_back(make_pair(-ta,i));
		else coords.push_back(make_pair(tb+pos.sc,i));
	}
	sort(coords.begin(),coords.end());
	for(int i = 1;i<N;i++){
		A[i-1] = coords[i-1].sc;
		B[i-1] = coords[i].sc;
		W[i-1] = coords[i].fs-coords[i-1].fs;
	}
	return;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 1995 out of 500000 queries used.
2 Incorrect 1 ms 472 KB Reported list of edges differ from actual.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 1995 out of 500000 queries used.
2 Incorrect 1 ms 472 KB Reported list of edges differ from actual.
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 1979 out of 12000 queries used.
2 Correct 1 ms 604 KB Correct: 1983 out of 12000 queries used.
3 Correct 1 ms 604 KB Correct: 1997 out of 12000 queries used.
4 Correct 1 ms 600 KB Correct: 1983 out of 12000 queries used.
5 Correct 1 ms 604 KB Correct: 1979 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 1979 out of 12000 queries used.
2 Correct 1 ms 604 KB Correct: 1983 out of 12000 queries used.
3 Correct 1 ms 604 KB Correct: 1997 out of 12000 queries used.
4 Correct 1 ms 600 KB Correct: 1983 out of 12000 queries used.
5 Correct 1 ms 604 KB Correct: 1979 out of 12000 queries used.
6 Correct 2 ms 600 KB Correct: 1993 out of 12000 queries used.
7 Correct 1 ms 600 KB Correct: 1989 out of 12000 queries used.
8 Correct 1 ms 604 KB Correct: 1997 out of 12000 queries used.
9 Correct 1 ms 600 KB Correct: 1991 out of 12000 queries used.
10 Correct 1 ms 600 KB Correct: 1985 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct: 1995 out of 500000 queries used.
2 Incorrect 1 ms 472 KB Reported list of edges differ from actual.
3 Halted 0 ms 0 KB -