oj.uz

Submission #958254

# Submission time Handle Problem Language Result Execution time Memory
958254 2024-04-05T08:30:51 Z 8pete8 Stations (IOI20_stations) C++17
76 / 100
 621 ms 1744 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;
vector<int>v,lab;
void dfs(int cur,int p){
	if(!lab[cur])tin[cur]=++t;
	for(auto i:adj[cur])if(i!=p)dfs(i,cur);
	if(lab[cur])tout[cur]=++t;
}
void dfs2(int cur,int p){
	for(auto i:adj[cur])if(i!=p)dfs(i,cur);
	if(lab[cur])tout[cur]=++t;
}
vector<int> label(int n, int k,vector<int> U,vector<int> V) {
	v.assign(n,0),lab.assign(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);
	dfs2(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: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=1;i<c.size();i++)if(c[i-1]<b&&b<=c[i])return c[i];
      |               ~^~~~~~~~~
stations.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   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 588 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1992
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 940 KB Output is correct
2 Correct 284 ms 936 KB Output is correct
3 Correct 606 ms 684 KB Output is correct
4 Correct 410 ms 684 KB Output is correct
5 Correct 413 ms 684 KB Output is correct
6 Correct 289 ms 936 KB Output is correct
7 Correct 277 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 405 ms 684 KB Output is correct
12 Correct 278 ms 1188 KB Output is correct
13 Correct 285 ms 1692 KB Output is correct
14 Correct 259 ms 684 KB Output is correct
15 Correct 36 ms 764 KB Output is correct
16 Correct 33 ms 940 KB Output is correct
17 Correct 55 ms 892 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 684 KB Output is correct
2 Correct 434 ms 684 KB Output is correct
3 Correct 376 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 409 ms 684 KB Output is correct
8 Correct 488 ms 684 KB Output is correct
9 Correct 441 ms 684 KB Output is correct
10 Correct 427 ms 684 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 2 ms 884 KB Output is correct
16 Correct 307 ms 796 KB Output is correct
17 Correct 333 ms 852 KB Output is correct
18 Correct 291 ms 684 KB Output is correct
19 Correct 314 ms 684 KB Output is correct
20 Correct 335 ms 684 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 330 ms 944 KB Partially correct
2 Partially correct 255 ms 928 KB Partially correct
3 Correct 547 ms 940 KB Output is correct
4 Correct 436 ms 684 KB Output is correct
5 Correct 363 ms 684 KB Output is correct
6 Partially correct 269 ms 932 KB Partially correct
7 Partially correct 288 ms 684 KB Partially correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Partially correct 321 ms 952 KB Partially correct
12 Partially correct 310 ms 1104 KB Partially correct
13 Correct 605 ms 684 KB Output is correct
14 Correct 407 ms 684 KB Output is correct
15 Correct 398 ms 684 KB Output is correct
16 Partially correct 255 ms 684 KB Partially correct
17 Correct 354 ms 684 KB Output is correct
18 Partially correct 311 ms 1044 KB Partially correct
19 Partially correct 299 ms 1300 KB Partially correct
20 Partially correct 256 ms 684 KB Partially correct
21 Correct 32 ms 768 KB Output is correct
22 Partially correct 36 ms 1192 KB Partially correct
23 Partially correct 66 ms 924 KB Partially correct
24 Correct 4 ms 768 KB Output is correct
25 Correct 4 ms 768 KB Output is correct
26 Correct 2 ms 768 KB Output is correct
27 Correct 3 ms 768 KB Output is correct
28 Correct 0 ms 764 KB Output is correct
29 Correct 328 ms 684 KB Output is correct
30 Correct 317 ms 684 KB Output is correct
31 Correct 336 ms 684 KB Output is correct
32 Correct 369 ms 944 KB Output is correct
33 Correct 301 ms 684 KB Output is correct
34 Partially correct 193 ms 932 KB Partially correct
35 Partially correct 287 ms 1208 KB Partially correct
36 Partially correct 315 ms 1040 KB Partially correct
37 Partially correct 308 ms 1048 KB Partially correct
38 Partially correct 346 ms 1176 KB Partially correct
39 Partially correct 297 ms 1276 KB Partially correct
40 Partially correct 285 ms 1416 KB Partially correct
41 Partially correct 293 ms 1024 KB Partially correct
42 Partially correct 33 ms 948 KB Partially correct
43 Partially correct 59 ms 888 KB Partially correct
44 Partially correct 94 ms 896 KB Partially correct
45 Partially correct 99 ms 916 KB Partially correct
46 Partially correct 202 ms 1116 KB Partially correct
47 Partially correct 210 ms 896 KB Partially correct
48 Partially correct 38 ms 1744 KB Partially correct
49 Partially correct 33 ms 1440 KB Partially correct