oj.uz

Submission #958247

# Submission time Handle Problem Language Result Execution time Memory
958247 2024-04-05T08:27:56 Z 8pete8 Stations (IOI20_stations) C++17
76 / 100
 564 ms 1528 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);
	t=-1;
	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:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i=1;i<c.size();i++)if(c[i-1]<b&&b<=c[i])return c[i];
      |               ~^~~~~~~~~
stations.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   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=1990
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 335 ms 920 KB Output is correct
2 Correct 321 ms 920 KB Output is correct
3 Correct 564 ms 940 KB Output is correct
4 Correct 395 ms 684 KB Output is correct
5 Correct 378 ms 684 KB Output is correct
6 Correct 317 ms 916 KB Output is correct
7 Correct 296 ms 684 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 350 ms 800 KB Output is correct
12 Correct 269 ms 1024 KB Output is correct
13 Correct 295 ms 1296 KB Output is correct
14 Correct 310 ms 684 KB Output is correct
15 Correct 34 ms 768 KB Output is correct
16 Correct 37 ms 932 KB Output is correct
17 Correct 57 ms 1148 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 684 KB Output is correct
2 Correct 484 ms 684 KB Output is correct
3 Correct 373 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 446 ms 684 KB Output is correct
8 Correct 551 ms 688 KB Output is correct
9 Correct 407 ms 684 KB Output is correct
10 Correct 395 ms 684 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 332 ms 864 KB Output is correct
17 Correct 337 ms 684 KB Output is correct
18 Correct 353 ms 1096 KB Output is correct
19 Correct 343 ms 684 KB Output is correct
20 Correct 323 ms 940 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 331 ms 928 KB Partially correct
2 Partially correct 288 ms 908 KB Partially correct
3 Correct 533 ms 688 KB Output is correct
4 Correct 453 ms 684 KB Output is correct
5 Correct 401 ms 688 KB Output is correct
6 Partially correct 290 ms 912 KB Partially correct
7 Partially correct 291 ms 684 KB Partially correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 4 ms 764 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Partially correct 279 ms 888 KB Partially correct
12 Partially correct 321 ms 1096 KB Partially correct
13 Correct 531 ms 684 KB Output is correct
14 Correct 422 ms 940 KB Output is correct
15 Correct 385 ms 684 KB Output is correct
16 Partially correct 280 ms 936 KB Partially correct
17 Correct 369 ms 936 KB Output is correct
18 Partially correct 287 ms 1152 KB Partially correct
19 Partially correct 298 ms 1308 KB Partially correct
20 Partially correct 265 ms 684 KB Partially correct
21 Correct 36 ms 764 KB Output is correct
22 Partially correct 41 ms 1164 KB Partially correct
23 Partially correct 68 ms 888 KB Partially correct
24 Correct 3 ms 768 KB Output is correct
25 Correct 3 ms 768 KB Output is correct
26 Correct 4 ms 768 KB Output is correct
27 Correct 3 ms 764 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 316 ms 684 KB Output is correct
30 Correct 335 ms 684 KB Output is correct
31 Correct 295 ms 684 KB Output is correct
32 Correct 323 ms 684 KB Output is correct
33 Correct 327 ms 684 KB Output is correct
34 Partially correct 213 ms 912 KB Partially correct
35 Partially correct 290 ms 1432 KB Partially correct
36 Partially correct 292 ms 1024 KB Partially correct
37 Partially correct 321 ms 1156 KB Partially correct
38 Partially correct 275 ms 1020 KB Partially correct
39 Partially correct 310 ms 1528 KB Partially correct
40 Partially correct 306 ms 1156 KB Partially correct
41 Partially correct 321 ms 1012 KB Partially correct
42 Partially correct 44 ms 900 KB Partially correct
43 Partially correct 65 ms 888 KB Partially correct
44 Partially correct 90 ms 900 KB Partially correct
45 Partially correct 110 ms 904 KB Partially correct
46 Partially correct 223 ms 860 KB Partially correct
47 Partially correct 196 ms 888 KB Partially correct
48 Partially correct 40 ms 1460 KB Partially correct
49 Partially correct 38 ms 1452 KB Partially correct