oj.uz

Submission #385953

# Submission time Handle Problem Language Result Execution time Memory
385953 2021-04-05T09:49:22 Z PedroBigMan Stations (IOI20_stations) C++14
10 / 100
 1047 ms 1012 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;
    }
};

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;
}

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 812 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 719 ms 992 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 756 KB Output is correct
2 Correct 749 ms 736 KB Output is correct
3 Correct 724 ms 868 KB Output is correct
4 Correct 3 ms 736 KB Output is correct
5 Correct 8 ms 756 KB Output is correct
6 Correct 2 ms 868 KB Output is correct
7 Correct 709 ms 756 KB Output is correct
8 Correct 1033 ms 736 KB Output is correct
9 Correct 794 ms 868 KB Output is correct
10 Correct 684 ms 864 KB Output is correct
11 Correct 6 ms 872 KB Output is correct
12 Correct 8 ms 796 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 736 KB Output is correct
16 Correct 703 ms 884 KB Output is correct
17 Correct 589 ms 864 KB Output is correct
18 Correct 548 ms 1012 KB Output is correct
19 Correct 675 ms 884 KB Output is correct
20 Correct 604 ms 736 KB Output is correct

Subtask #5
0 / 61.0

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