oj.uz

Submission #964704

# Submission time Handle Problem Language Result Execution time Memory
964704 2024-04-17T11:30:13 Z 8pete8 City Mapping (NOI18_citymapping) C++17
75.11 / 100
 23 ms 860 KB 
#include "citymapping.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
//#define double long double
const int mxn=2e3,inf=1e18;
vector<int>on;
int sz[mxn+10],del[mxn+10],D[mxn+10],up[mxn+10];
vector<pair<pii,int>>e;
vector<int>adj[mxn+10];
vector<int>von;
int cnt=0;
int n;
void getsz(int cur,int p){
	sz[cur]=1;
	cnt++;
	on.pb(cur);
	for(auto i:adj[cur]){
		if(del[i]||i==p)continue;
		up[i]=cur;
		getsz(i,cur);
		sz[cur]+=sz[i];
	}
}
int qnode,last;
void solve(int node){
	on.clear();
	cnt=0;
	getsz(node,-1);
	pii ed={inf,-1};
	up[node]=-1;
	if(on.size()==1){
		int y=get_distance(node,qnode);
		e.pb({{qnode,node},y});
		adj[node].pb(qnode);
		adj[qnode].pb(node);
		return;
	}
	for(auto i:on)ed=min(ed,{abs((cnt/2)-sz[i]),i});
	int x=get_distance(ed.s,qnode);
	if(D[qnode]==D[ed.s]+x){
		del[up[ed.s]]=1;
		for(int i=1;i<=n;i++)if(i!=ed.s)D[i]-=D[ed.s];
		solve(ed.s);
	}
	else{
		del[ed.s]=1;
		solve(node);
	}
}
void find_roads(int32_t N, int32_t q, int32_t A[], int32_t B[], int32_t W[]){
	n=N;
	srand(time(NULL));
	int st=rand()%n;
	st++;
	vector<pii>o;
	for(int i=1;i<=n;i++)if(i!=st)o.pb({get_distance(i,st),i});
	sort(all(o));
	for(auto i:o){
		qnode=i.s;
		for(int i=1;i<=n;i++)del[i]=0;
		D[st]=0;
		for(auto i:o)D[i.s]=i.f;
		solve(st);
	}
	for(int i=0;i<e.size();i++)A[i]=e[i].f.f,B[i]=e[i].f.s,W[i]=e[i].s;
	return;
}

Compilation message

citymapping.cpp: In function 'void find_roads(int32_t, int32_t, int32_t*, int32_t*, int32_t*)':
citymapping.cpp:99:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i=0;i<e.size();i++)A[i]=e[i].f.f,B[i]=e[i].f.s,W[i]=e[i].s;
      |              ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 804 KB Correct: 9965 out of 500000 queries used.
2 Correct 18 ms 792 KB Correct: 10313 out of 500000 queries used.
3 Correct 15 ms 604 KB Correct: 10431 out of 500000 queries used.
4 Correct 14 ms 604 KB Correct: 10488 out of 500000 queries used.
5 Correct 18 ms 604 KB Correct: 10150 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 804 KB Correct: 9965 out of 500000 queries used.
2 Correct 18 ms 792 KB Correct: 10313 out of 500000 queries used.
3 Correct 15 ms 604 KB Correct: 10431 out of 500000 queries used.
4 Correct 14 ms 604 KB Correct: 10488 out of 500000 queries used.
5 Correct 18 ms 604 KB Correct: 10150 out of 500000 queries used.
6 Correct 17 ms 604 KB Correct: 9937 out of 500000 queries used.
7 Correct 19 ms 804 KB Correct: 10301 out of 500000 queries used.
8 Correct 22 ms 612 KB Correct: 10479 out of 500000 queries used.
9 Correct 14 ms 600 KB Correct: 10429 out of 500000 queries used.
10 Correct 22 ms 604 KB Correct: 10132 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 800 KB Correct: 9878 out of 12000 queries used.
2 Correct 19 ms 796 KB Correct: 9904 out of 12000 queries used.
3 Correct 18 ms 792 KB Correct: 9976 out of 12000 queries used.
4 Correct 20 ms 768 KB Correct: 9904 out of 12000 queries used.
5 Correct 18 ms 604 KB Correct: 9878 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 800 KB Correct: 9878 out of 12000 queries used.
2 Correct 19 ms 796 KB Correct: 9904 out of 12000 queries used.
3 Correct 18 ms 792 KB Correct: 9976 out of 12000 queries used.
4 Correct 20 ms 768 KB Correct: 9904 out of 12000 queries used.
5 Correct 18 ms 604 KB Correct: 9878 out of 12000 queries used.
6 Correct 23 ms 800 KB Correct: 9957 out of 12000 queries used.
7 Correct 17 ms 600 KB Correct: 9938 out of 12000 queries used.
8 Correct 21 ms 600 KB Correct: 9979 out of 12000 queries used.
9 Correct 17 ms 600 KB Correct: 9947 out of 12000 queries used.
10 Correct 17 ms 604 KB Correct: 9914 out of 12000 queries used.

Subtask #5
18.11 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 804 KB Correct: 9965 out of 500000 queries used.
2 Correct 18 ms 792 KB Correct: 10313 out of 500000 queries used.
3 Correct 15 ms 604 KB Correct: 10431 out of 500000 queries used.
4 Correct 14 ms 604 KB Correct: 10488 out of 500000 queries used.
5 Correct 18 ms 604 KB Correct: 10150 out of 500000 queries used.
6 Correct 17 ms 604 KB Correct: 9937 out of 500000 queries used.
7 Correct 19 ms 804 KB Correct: 10301 out of 500000 queries used.
8 Correct 22 ms 612 KB Correct: 10479 out of 500000 queries used.
9 Correct 14 ms 600 KB Correct: 10429 out of 500000 queries used.
10 Correct 22 ms 604 KB Correct: 10132 out of 500000 queries used.
11 Correct 20 ms 800 KB Correct: 9878 out of 12000 queries used.
12 Correct 19 ms 796 KB Correct: 9904 out of 12000 queries used.
13 Correct 18 ms 792 KB Correct: 9976 out of 12000 queries used.
14 Correct 20 ms 768 KB Correct: 9904 out of 12000 queries used.
15 Correct 18 ms 604 KB Correct: 9878 out of 12000 queries used.
16 Correct 23 ms 800 KB Correct: 9957 out of 12000 queries used.
17 Correct 17 ms 600 KB Correct: 9938 out of 12000 queries used.
18 Correct 21 ms 600 KB Correct: 9979 out of 12000 queries used.
19 Correct 17 ms 600 KB Correct: 9947 out of 12000 queries used.
20 Correct 17 ms 604 KB Correct: 9914 out of 12000 queries used.
21 Correct 19 ms 604 KB Correct: 9934 out of 25000 queries used.
22 Correct 22 ms 604 KB Correct: 10296 out of 25000 queries used.
23 Correct 20 ms 788 KB Correct: 10238 out of 25000 queries used.
24 Correct 17 ms 600 KB Correct: 10212 out of 25000 queries used.
25 Correct 19 ms 756 KB Correct: 10464 out of 25000 queries used.
26 Correct 15 ms 604 KB Correct: 10362 out of 25000 queries used.
27 Correct 22 ms 720 KB Correct: 10454 out of 25000 queries used.
28 Correct 15 ms 768 KB Correct: 10512 out of 25000 queries used.
29 Correct 15 ms 776 KB Correct: 10454 out of 25000 queries used.
30 Correct 20 ms 600 KB Correct: 10436 out of 25000 queries used.
31 Correct 18 ms 604 KB Correct: 10504 out of 25000 queries used.
32 Correct 18 ms 812 KB Correct: 9928 out of 25000 queries used.
33 Correct 14 ms 600 KB Correct: 10475 out of 25000 queries used.
34 Correct 15 ms 600 KB Correct: 10489 out of 25000 queries used.
35 Correct 14 ms 604 KB Correct: 10471 out of 25000 queries used.
36 Correct 14 ms 588 KB Correct: 10430 out of 25000 queries used.
37 Correct 14 ms 604 KB Correct: 10444 out of 25000 queries used.
38 Correct 14 ms 608 KB Correct: 10454 out of 25000 queries used.
39 Correct 15 ms 776 KB Correct: 10488 out of 25000 queries used.
40 Correct 14 ms 592 KB Correct: 10481 out of 25000 queries used.
41 Correct 14 ms 684 KB Correct: 10511 out of 25000 queries used.
42 Correct 14 ms 604 KB Correct: 10437 out of 25000 queries used.
43 Correct 18 ms 604 KB Correct: 9958 out of 25000 queries used.
44 Correct 14 ms 604 KB Correct: 10393 out of 25000 queries used.
45 Correct 14 ms 604 KB Correct: 10438 out of 25000 queries used.
46 Correct 14 ms 604 KB Correct: 10365 out of 25000 queries used.
47 Correct 15 ms 604 KB Correct: 10486 out of 25000 queries used.
48 Correct 14 ms 600 KB Correct: 10451 out of 25000 queries used.
49 Correct 14 ms 856 KB Correct: 10441 out of 25000 queries used.
50 Correct 14 ms 604 KB Correct: 10497 out of 25000 queries used.
51 Correct 14 ms 604 KB Correct: 10468 out of 25000 queries used.
52 Correct 19 ms 604 KB Correct: 10506 out of 25000 queries used.
53 Correct 18 ms 604 KB Correct: 10502 out of 25000 queries used.
54 Correct 17 ms 792 KB Correct: 10300 out of 25000 queries used.
55 Correct 19 ms 612 KB Correct: 10440 out of 25000 queries used.
56 Correct 16 ms 600 KB Correct: 10432 out of 25000 queries used.
57 Correct 14 ms 604 KB Correct: 10513 out of 25000 queries used.
58 Correct 15 ms 776 KB Correct: 10399 out of 25000 queries used.
59 Correct 14 ms 600 KB Correct: 10441 out of 25000 queries used.
60 Correct 23 ms 776 KB Correct: 10119 out of 25000 queries used.
61 Correct 18 ms 604 KB Correct: 10070 out of 25000 queries used.
62 Correct 22 ms 860 KB Correct: 10060 out of 25000 queries used.
63 Correct 18 ms 600 KB Correct: 10140 out of 25000 queries used.
64 Correct 18 ms 600 KB Correct: 10102 out of 25000 queries used.
65 Correct 20 ms 796 KB Correct: 10239 out of 25000 queries used.
66 Correct 21 ms 792 KB Correct: 10112 out of 25000 queries used.
67 Correct 17 ms 600 KB Correct: 10265 out of 25000 queries used.
68 Correct 17 ms 604 KB Correct: 10241 out of 25000 queries used.
69 Correct 22 ms 788 KB Correct: 10309 out of 25000 queries used.
70 Correct 18 ms 788 KB Correct: 10225 out of 25000 queries used.