oj.uz

Submission #432444

# Submission time Handle Problem Language Result Execution time Memory
432444 2021-06-18T09:59:53 Z Pbezz Stations (IOI20_stations) C++14
16 / 100
 973 ms 680 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN = 1005;
const ll INF = 1e9+7;
vector<vector<ll>>adj(MAXN);
int deg[MAXN],order[MAXN];

void dfs(int node, int p,int mark){
order[node]=mark;
for(auto u:adj[node]){
if(u==p)continue;

dfs(u,node,mark+1);

}
}


std::vector<int> label(int n, int k,std::vector<int>u,std::vector<int>v){
	std::vector<int> labels(n);
	int i;

	for(i=0;i<n;i++) {
	deg[i]=0;
	adj[i].clear();
	order[i]=0;
	}


	for(i=0;i<n-1;i++){
	adj[u[i]].pb(v[i]);
	adj[v[i]].pb(u[i]);
	deg[u[i]]++;
	deg[v[i]]++;
	}

	for(i=0;i<n;i++) {
	if(deg[i]>2)break;
	}

	if(i!=n){
	int cur=1000;
	for(auto u:adj[i]){
	dfs(u,i,cur);
	cur+=1000;
	}
	order[i]=0;


	}else{

	for(i=0;i<n;i++) {
	if(deg[i]==1)break;
	}
	int cur=1000;
	for(auto u:adj[i]){
	dfs(u,i,cur);
	cur+=1000;
	}
	order[i]=0;
	}
	for (i = 0; i < n; i++) {
		labels[i] = order[i];
	//cout<<order[i]<<" ";
	}//cout<<endl;
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {

	if(s==0){
	int ans=(int)(t/1000);//cout<<t<<" "<<ans<<"haha\n";
	return 1000*ans;
	}

	int mini=INF,maxi=-1,tt=t/1000,ss=s/1000;
	for(auto u:c){
	mini=min(mini,u);
	maxi=max(maxi,u);
	}

	if(tt==ss&&t>s)return maxi;

	return mini;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 312 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=1007
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 308 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=2, label=1001
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 516 KB Output is correct
2 Correct 453 ms 520 KB Output is correct
3 Correct 884 ms 400 KB Output is correct
4 Correct 640 ms 404 KB Output is correct
5 Correct 569 ms 400 KB Output is correct
6 Correct 493 ms 508 KB Output is correct
7 Correct 465 ms 528 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 647 ms 400 KB Output is correct
12 Correct 475 ms 656 KB Output is correct
13 Correct 495 ms 632 KB Output is correct
14 Correct 458 ms 516 KB Output is correct
15 Correct 58 ms 528 KB Output is correct
16 Correct 69 ms 548 KB Output is correct
17 Correct 113 ms 644 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 973 ms 508 KB Output is correct
2 Correct 707 ms 400 KB Output is correct
3 Correct 668 ms 656 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 612 ms 516 KB Output is correct
8 Correct 972 ms 536 KB Output is correct
9 Correct 735 ms 400 KB Output is correct
10 Correct 646 ms 400 KB Output is correct
11 Incorrect 1 ms 200 KB Invalid labels (duplicates values). scenario=5, label=1001
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 593 ms 508 KB Partially correct
2 Partially correct 479 ms 680 KB Partially correct
3 Correct 932 ms 520 KB Output is correct
4 Partially correct 657 ms 400 KB Partially correct
5 Partially correct 607 ms 532 KB Partially correct
6 Partially correct 481 ms 520 KB Partially correct
7 Partially correct 462 ms 520 KB Partially correct
8 Partially correct 3 ms 468 KB Partially correct
9 Partially correct 4 ms 468 KB Partially correct
10 Partially correct 3 ms 464 KB Partially correct
11 Incorrect 6 ms 304 KB Invalid labels (duplicates values). scenario=0, label=1002
12 Halted 0 ms 0 KB -