oj.uz

Submission #958242

# Submission time Handle Problem Language Result Execution time Memory
958242 2024-04-05T08:25:14 Z 8pete8 Stations (IOI20_stations) C++17
67.2269 / 100
 640 ms 1548 KB 
#include "stations.h"
#include <vector>
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<numeric> //gcd(a,b)
#include<cmath>
#include<set>
#include<cassert>
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
const int mxn=1e3;
vector<int>adj[mxn+10];
int tin[mxn+10],tout[mxn+10],t=-1;
void dfs(int cur,int p){
	tin[cur]=++t;
	for(auto i:adj[cur])if(i!=p)dfs(i,cur);
	tout[cur]=++t;
}
vector<int> label(int n, int k,vector<int> U,vector<int> V) {
	vector<int>v(n,0),lab(n,0);
	for(int i=0;i<n-1;i++)adj[U[i]].pb(V[i]),adj[V[i]].pb(U[i]);
	
	queue<pii>q;
	lab[0]=1;
	q.push({0,0});
	while(!q.empty()){
		int cur=q.front().f,p=q.front().s;
		q.pop();
		lab[cur]=lab[p]^1;
		for(auto i:adj[cur])if(i!=p)q.push({i,cur});
	}
	dfs(0,-1);
	for(int i=0;i<n;i++)v[i]=((lab[i])?tout[i]:tin[i]);
	for(int i=0;i<n;i++)adj[i].clear();
	return v;
}
int find_next_station(int a, int b, vector<int> c){
	if(a<c[0]){
		
		//a is tin,other is tout
		if(b<a||b>=c.back())return c.back();//out side subtree
		for(int i=1;i<c.size();i++)if(c[i-1]<b&&b<=c[i])return c[i];
		return c[0];
	}
	else{
		
		//a is tout,other is tin
		if(b>a||b<=c[0])return c[0];
		for(int i=0;i<c.size()-1;i++)if(c[i]<=b&&b<c[i+1])return c[i];
		return c.back();
	}
}/*
int main(){
	int n,k;cin>>n>>k;
	vector<int>a(n-1),b(n-1);
	for(int i=0;i<n-1;i++)cin>>a[i];
	for(int i=0;i<n-1;i++)cin>>b[i];
	vector<int>bruh=label(n,k,a,b);
	for(auto i:bruh)cout<<i<<" ";
	vector<int>g;
	for(auto i:adj[1])g.pb(bruh[i]);
	cout<<find_next_station(9,7,g)<<"B\n";
}*/

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=1;i<c.size();i++)if(c[i-1]<b&&b<=c[i])return c[i];
      |               ~^~~~~~~~~
stations.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=0;i<c.size()-1;i++)if(c[i]<=b&&b<c[i+1])return c[i];
      |               ~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 916 KB Output is correct
2 Correct 309 ms 920 KB Output is correct
3 Correct 589 ms 684 KB Output is correct
4 Correct 438 ms 692 KB Output is correct
5 Correct 416 ms 684 KB Output is correct
6 Correct 305 ms 912 KB Output is correct
7 Correct 279 ms 936 KB Output is correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 764 KB Output is correct
11 Correct 360 ms 684 KB Output is correct
12 Correct 288 ms 1032 KB Output is correct
13 Correct 303 ms 1164 KB Output is correct
14 Correct 290 ms 684 KB Output is correct
15 Correct 31 ms 768 KB Output is correct
16 Correct 36 ms 936 KB Output is correct
17 Correct 58 ms 916 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 684 KB Output is correct
2 Correct 422 ms 684 KB Output is correct
3 Correct 413 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 404 ms 684 KB Output is correct
8 Correct 557 ms 940 KB Output is correct
9 Correct 435 ms 684 KB Output is correct
10 Correct 379 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 4 ms 764 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 2 ms 772 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 304 ms 684 KB Output is correct
17 Correct 321 ms 684 KB Output is correct
18 Correct 332 ms 688 KB Output is correct
19 Correct 323 ms 936 KB Output is correct
20 Correct 336 ms 684 KB Output is correct

Subtask #5
41.2269 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 344 ms 916 KB Partially correct
2 Partially correct 310 ms 912 KB Partially correct
3 Correct 576 ms 684 KB Output is correct
4 Correct 422 ms 684 KB Output is correct
5 Correct 385 ms 684 KB Output is correct
6 Partially correct 304 ms 912 KB Partially correct
7 Partially correct 301 ms 688 KB Partially correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Partially correct 332 ms 880 KB Partially correct
12 Partially correct 355 ms 844 KB Partially correct
13 Correct 640 ms 684 KB Output is correct
14 Correct 425 ms 684 KB Output is correct
15 Correct 359 ms 684 KB Output is correct
16 Partially correct 267 ms 684 KB Partially correct
17 Correct 401 ms 684 KB Output is correct
18 Partially correct 311 ms 1260 KB Partially correct
19 Partially correct 321 ms 1292 KB Partially correct
20 Partially correct 250 ms 684 KB Partially correct
21 Partially correct 32 ms 768 KB Partially correct
22 Partially correct 40 ms 1156 KB Partially correct
23 Partially correct 64 ms 1088 KB Partially correct
24 Correct 3 ms 768 KB Output is correct
25 Correct 3 ms 772 KB Output is correct
26 Correct 3 ms 764 KB Output is correct
27 Correct 2 ms 764 KB Output is correct
28 Correct 0 ms 768 KB Output is correct
29 Correct 324 ms 684 KB Output is correct
30 Correct 312 ms 684 KB Output is correct
31 Correct 359 ms 684 KB Output is correct
32 Correct 336 ms 684 KB Output is correct
33 Correct 306 ms 932 KB Output is correct
34 Partially correct 217 ms 912 KB Partially correct
35 Partially correct 244 ms 1548 KB Partially correct
36 Partially correct 308 ms 1028 KB Partially correct
37 Partially correct 287 ms 1356 KB Partially correct
38 Partially correct 327 ms 1168 KB Partially correct
39 Partially correct 338 ms 1028 KB Partially correct
40 Partially correct 268 ms 1024 KB Partially correct
41 Partially correct 304 ms 1016 KB Partially correct
42 Partially correct 37 ms 952 KB Partially correct
43 Partially correct 67 ms 892 KB Partially correct
44 Partially correct 67 ms 900 KB Partially correct
45 Partially correct 96 ms 912 KB Partially correct
46 Partially correct 218 ms 872 KB Partially correct
47 Partially correct 192 ms 888 KB Partially correct
48 Partially correct 37 ms 1520 KB Partially correct
49 Partially correct 38 ms 1268 KB Partially correct