oj.uz

Submission #385958

# Submission time Handle Problem Language Result Execution time Memory
385958 2021-04-05T09:53:08 Z PedroBigMan Stations (IOI20_stations) C++14
10 / 100
 1065 ms 1392 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(T.pos[i].ff*mil+T.pos[i].ss);}
	REP(i,0,N) {label[i]=f(label[i]);}
	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;
	REP(i,0,c.size()) {c[i]=invf(c[i]);}
	s=invf(s); t=invf(t);
	self={s/mil,s%mil};
	REP(i,0,c.size()) {inter.pb({c[i]/mil,c[i]%mil});}
	target={t/mil,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 f(c[i]);}
	}
	return f(c[ind]);
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 8 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 690 ms 1064 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1065 ms 868 KB Output is correct
2 Correct 759 ms 868 KB Output is correct
3 Correct 631 ms 868 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 5 ms 736 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 729 ms 756 KB Output is correct
8 Correct 905 ms 756 KB Output is correct
9 Correct 705 ms 996 KB Output is correct
10 Correct 663 ms 736 KB Output is correct
11 Correct 6 ms 872 KB Output is correct
12 Correct 7 ms 736 KB Output is correct
13 Correct 5 ms 756 KB Output is correct
14 Correct 4 ms 864 KB Output is correct
15 Correct 3 ms 756 KB Output is correct
16 Correct 496 ms 756 KB Output is correct
17 Correct 555 ms 876 KB Output is correct
18 Correct 608 ms 872 KB Output is correct
19 Correct 619 ms 756 KB Output is correct
20 Correct 697 ms 864 KB Output is correct

Subtask #5
0 / 61.0

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