oj.uz

Submission #958228

# Submission time Handle Problem Language Result Execution time Memory
958228 2024-04-05T08:01:15 Z 8pete8 Stations (IOI20_stations) C++17
0 / 100
 3000 ms 863284 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]);
	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)return c.back();//out side subtree
		auto it=ub(all(c),b)-1;
		return (*it);
	}
	else{
		//a is tout,other is tin
		if(b>a)return c[0];
		auto it=lb(all(c),b);
		return (*it);
	}
}/*
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";
}*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 863284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2580 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 684 KB Output is correct
2 Execution timed out 3064 ms 571408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 51592 KB Time limit exceeded
2 Halted 0 ms 0 KB -