oj.uz

Submission #1041314

# Submission time Handle Problem Language Result Execution time Memory
1041314 2024-08-01T21:05:27 Z HD1 Stations (IOI20_stations) C++14
21 / 100
 513 ms 50852 KB 
#include "stations.h"
#include<bits/stdc++.h>
#define ss second
#define all(s) s.begin(),s.end()
#define sz(s) ll(s.size())
#define pb push_back
typedef long long ll;
const ll MAX=1e6;
using namespace std;
ll marc=1, q;
vector<ll> gfo[MAX];
ll m[MAX];
bool vst[MAX];
void dfs(int u, int f){
	m[u]=marc;
	//cout<<u<<'.'<<m[u]<<' ';
	for(auto v:gfo[u]){
		if(v!=f){
			marc+=q;
			dfs(v,u);
		}
	}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
	vector<int> labels(n);
	for(int i=0; i<sz(u); i++){
		gfo[u[i]].pb(v[i]);
		gfo[v[i]].pb(u[i]);
	}
	bool xd=false;
	for(int i=0; i<n; i++){
		if(sz(gfo[i])>2){
			//cout<<i<<'\n';
			q=sz(gfo[i]);
			m[i]=0;
			for(int j=0; j<sz(gfo[i]); j++){
				int v=gfo[i][j];
				marc=j+1;
				dfs(v, i);
				//cout<<'\n';
			}
			xd=true;
			break;
		}
	}
	if(!xd){
		marc=1;
		q=1;
		for(int i=0; i<n; i++){
			if(sz(gfo[i])==1 && m[i]==0) dfs(i, i);
		}
		
	}
	for(int i=0; i<n; i++){
		labels[i]=m[i];
		m[i]=0;
		gfo[i].clear();
	}
	return labels;
}
int find_next_station(int s, int t, vector<int> c){
	sort(all(c));
	// cout<<s<<' '<<t<<' '<<' ';
	// for(auto x:c){
	// 	cout<<x<<' ';
	// }
	// cout<<'\n';
	ll md=abs(c[sz(c)-1]-s);
	if(s==0 || t==0){
		if(s==0){
			for(auto x:c){
				if(x%md==t%md){
					return x;
				}
			}
		}
		return c[0];
	}
	if(s%md != t%md){
		return c[0];
	}
	if(t>s){
		return c[sz(c)-1];
	}
	return c[0];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 48560 KB Output is correct
2 Correct 257 ms 48556 KB Output is correct
3 Correct 510 ms 48300 KB Output is correct
4 Correct 377 ms 48300 KB Output is correct
5 Correct 345 ms 48300 KB Output is correct
6 Correct 205 ms 48808 KB Output is correct
7 Correct 281 ms 48556 KB Output is correct
8 Correct 8 ms 48400 KB Output is correct
9 Correct 8 ms 48504 KB Output is correct
10 Correct 8 ms 48392 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 48556 KB Output is correct
2 Correct 253 ms 48556 KB Output is correct
3 Correct 513 ms 48300 KB Output is correct
4 Correct 400 ms 48300 KB Output is correct
5 Correct 361 ms 48300 KB Output is correct
6 Correct 236 ms 48556 KB Output is correct
7 Correct 261 ms 48556 KB Output is correct
8 Correct 8 ms 48400 KB Output is correct
9 Correct 9 ms 48400 KB Output is correct
10 Correct 7 ms 48400 KB Output is correct
11 Correct 344 ms 48300 KB Output is correct
12 Correct 263 ms 50788 KB Output is correct
13 Correct 277 ms 50852 KB Output is correct
14 Correct 279 ms 50348 KB Output is correct
15 Correct 32 ms 50436 KB Output is correct
16 Correct 38 ms 48332 KB Output is correct
17 Correct 61 ms 48672 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 48484 KB Output is correct
2 Correct 365 ms 48388 KB Output is correct
3 Correct 322 ms 48488 KB Output is correct
4 Correct 9 ms 48384 KB Output is correct
5 Correct 11 ms 48384 KB Output is correct
6 Correct 9 ms 48392 KB Output is correct
7 Correct 279 ms 50348 KB Output is correct
8 Correct 513 ms 48300 KB Output is correct
9 Correct 369 ms 48300 KB Output is correct
10 Correct 361 ms 48300 KB Output is correct
11 Incorrect 15 ms 50432 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 48556 KB Output is correct
2 Correct 287 ms 48556 KB Output is correct
3 Correct 483 ms 48300 KB Output is correct
4 Correct 380 ms 48300 KB Output is correct
5 Correct 324 ms 48300 KB Output is correct
6 Correct 288 ms 48556 KB Output is correct
7 Correct 261 ms 48556 KB Output is correct
8 Correct 8 ms 48388 KB Output is correct
9 Correct 9 ms 48396 KB Output is correct
10 Correct 8 ms 48392 KB Output is correct
11 Incorrect 267 ms 50604 KB Wrong query response.
12 Halted 0 ms 0 KB -