oj.uz

Submission #958241

# Submission time Handle Problem Language Result Execution time Memory
958241 2024-04-05T08:23:42 Z 8pete8 Stations (IOI20_stations) C++17
67.2267 / 100
 574 ms 1432 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=0;
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=2017
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 916 KB Output is correct
2 Correct 266 ms 912 KB Output is correct
3 Correct 563 ms 684 KB Output is correct
4 Correct 417 ms 684 KB Output is correct
5 Correct 395 ms 684 KB Output is correct
6 Correct 323 ms 908 KB Output is correct
7 Correct 270 ms 684 KB Output is correct
8 Correct 2 ms 964 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 2 ms 764 KB Output is correct
11 Correct 374 ms 684 KB Output is correct
12 Correct 300 ms 1028 KB Output is correct
13 Correct 287 ms 1276 KB Output is correct
14 Correct 291 ms 684 KB Output is correct
15 Correct 29 ms 768 KB Output is correct
16 Correct 39 ms 876 KB Output is correct
17 Correct 58 ms 1196 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 684 KB Output is correct
2 Correct 424 ms 684 KB Output is correct
3 Correct 398 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 368 ms 684 KB Output is correct
8 Correct 548 ms 684 KB Output is correct
9 Correct 424 ms 684 KB Output is correct
10 Correct 391 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 308 ms 684 KB Output is correct
17 Correct 333 ms 684 KB Output is correct
18 Correct 346 ms 684 KB Output is correct
19 Correct 341 ms 936 KB Output is correct
20 Correct 351 ms 684 KB Output is correct

Subtask #5
41.2267 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 341 ms 1084 KB Partially correct
2 Partially correct 281 ms 908 KB Partially correct
3 Correct 538 ms 684 KB Output is correct
4 Correct 408 ms 684 KB Output is correct
5 Correct 400 ms 860 KB Output is correct
6 Partially correct 278 ms 916 KB Partially correct
7 Partially correct 307 ms 684 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 308 ms 884 KB Partially correct
12 Partially correct 341 ms 848 KB Partially correct
13 Correct 574 ms 684 KB Output is correct
14 Correct 423 ms 940 KB Output is correct
15 Correct 381 ms 684 KB Output is correct
16 Partially correct 287 ms 688 KB Partially correct
17 Correct 370 ms 892 KB Output is correct
18 Partially correct 299 ms 1008 KB Partially correct
19 Partially correct 285 ms 1288 KB Partially correct
20 Partially correct 280 ms 684 KB Partially correct
21 Partially correct 33 ms 764 KB Partially correct
22 Partially correct 37 ms 936 KB Partially correct
23 Partially correct 65 ms 880 KB Partially correct
24 Correct 4 ms 768 KB Output is correct
25 Correct 4 ms 768 KB Output is correct
26 Correct 3 ms 768 KB Output is correct
27 Correct 3 ms 768 KB Output is correct
28 Correct 2 ms 764 KB Output is correct
29 Correct 323 ms 684 KB Output is correct
30 Correct 351 ms 684 KB Output is correct
31 Correct 343 ms 684 KB Output is correct
32 Correct 330 ms 684 KB Output is correct
33 Correct 373 ms 684 KB Output is correct
34 Partially correct 196 ms 912 KB Partially correct
35 Partially correct 282 ms 1432 KB Partially correct
36 Partially correct 282 ms 1012 KB Partially correct
37 Partially correct 281 ms 1032 KB Partially correct
38 Partially correct 273 ms 1036 KB Partially correct
39 Partially correct 308 ms 1212 KB Partially correct
40 Partially correct 306 ms 1040 KB Partially correct
41 Partially correct 292 ms 1016 KB Partially correct
42 Partially correct 34 ms 900 KB Partially correct
43 Partially correct 62 ms 920 KB Partially correct
44 Partially correct 83 ms 1236 KB Partially correct
45 Partially correct 110 ms 904 KB Partially correct
46 Partially correct 210 ms 868 KB Partially correct
47 Partially correct 199 ms 888 KB Partially correct
48 Partially correct 35 ms 1268 KB Partially correct
49 Partially correct 33 ms 1360 KB Partially correct