oj.uz

Submission #385971

# Submission time Handle Problem Language Result Execution time Memory
385971 2021-04-05T10:02:57 Z PedroBigMan Stations (IOI20_stations) C++14
10 / 100
 1016 ms 1064 KB 
#include "stations.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;
 
template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
 
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
 
class Tree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<ll> > sons;
    vector<vector<ll> > adj;
    ll root;
    vector<bool> visited;
    vector<ll> DFSarr1; //DFS Array
	vector<pl> pos;
    
    Tree(vector<vector<ll> > ad, ll r=0LL)
    {
        N=ad.size(); root=r; adj=ad;
        REP(i,0,N) {visited.pb(false);}
        vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1);pos.pb({-1,-1});}
        DFS_Build(r,r);
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
    }
    
    void DFS_Build(ll s, ll par)
    {
		pos[s].ff=DFSarr1.size();
        DFSarr1.pb(s); 
        p[s]=par;
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(adj[s][i]==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i],s);
        }
		pos[s].ss=DFSarr1.size()-1;
        return;
    }
};

inline ll f(ll x)
{
	ll mil=1000;
	ll a = x/mil; ll b =x%mil;
	ll ans  =((2001-a)*a)/2 + (b-a);
	return ans;
}

inline ll invf(ll x)
{
	ll a,b; a=-1;
	REP(i,0,1000)
	{
		ll val = (i*(1999-i))/2;
		if(val>x) {a=i-1; break;}
	}
	if(a==-1) {a=999;}
	ll val = (a*(1999-a))/2; b=x-val;
	ll mil=1000;
	ll ans = mil*a+b;
	return ans;
}
 
vector<ll> label(ll N, ll k, vector<ll> u, vector<ll> v) 
{
	vector<ll> xx; vector<vector<ll> > adj; REP(i,0,N) {adj.pb(xx);}
	REP(i,0,N-1) {adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);}
	Tree T(adj); 
	vector<ll> label; 
	ll mil=1000;
	REP(i,0,N) {label.pb(f(T.pos[i].ff*mil+T.pos[i].ss));}
	return label;
}
 
ll find_next_station(ll s, ll t, vector<ll> c) 
{
	vector<pl> inter; pl self; pl target;
	ll mil=1000;
	vector<pl> poss;
	self={invf(s)/mil,invf(s)%mil};
	REP(i,0,c.size()) {inter.pb({invf(c[i])/mil,invf(c[i])%mil});}
	target={invf(t)/mil,invf(t)%mil}; 
	ll beg = min_element(whole(inter))->ff;
	ll maxend =-1;  ll ind;
	REP(i,0,inter.size()) {if(inter[i].ff==beg && inter[i].ss>maxend) {maxend=inter[i].ss; ind=i;}}
	REP(i,0,inter.size())
	{
		if(i==ind) {continue;}
		if(target.ff>=inter[i].ff && target.ss<=inter[i].ss) {return c[i];}
	}
	return c[ind];
}

Compilation message

stations.cpp: In function 'll find_next_station(ll, ll, std::vector<int>)':
stations.cpp:137:14: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  137 |  return c[ind];
      |              ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 518 ms 1004 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 868 KB Output is correct
2 Correct 709 ms 756 KB Output is correct
3 Correct 738 ms 868 KB Output is correct
4 Correct 3 ms 736 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 788 ms 876 KB Output is correct
8 Correct 994 ms 868 KB Output is correct
9 Correct 743 ms 756 KB Output is correct
10 Correct 831 ms 864 KB Output is correct
11 Correct 7 ms 864 KB Output is correct
12 Correct 7 ms 1036 KB Output is correct
13 Correct 5 ms 736 KB Output is correct
14 Correct 5 ms 736 KB Output is correct
15 Correct 3 ms 756 KB Output is correct
16 Correct 642 ms 756 KB Output is correct
17 Correct 615 ms 884 KB Output is correct
18 Correct 622 ms 756 KB Output is correct
19 Correct 604 ms 868 KB Output is correct
20 Correct 550 ms 736 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 703 ms 1064 KB Wrong query response.
2 Halted 0 ms 0 KB -