oj.uz

Submission #385960

# Submission time Handle Problem Language Result Execution time Memory
385960 2021-04-05T09:56:12 Z PedroBigMan Stations (IOI20_stations) C++14
10 / 100
 1233 ms 1192 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]);}
	REP(i,0,N) {label[i]=invf(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]);}
	REP(i,0,c.size()) {c[i]=f(c[i]);}
	s=invf(s); t=invf(t); s=f(s); t=f(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 c[i];}
	}
	return c[ind];
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1192 ms 884 KB Output is correct
2 Correct 769 ms 848 KB Output is correct
3 Correct 647 ms 868 KB Output is correct
4 Correct 4 ms 868 KB Output is correct
5 Correct 6 ms 868 KB Output is correct
6 Correct 2 ms 756 KB Output is correct
7 Correct 625 ms 756 KB Output is correct
8 Correct 1233 ms 756 KB Output is correct
9 Correct 763 ms 868 KB Output is correct
10 Correct 767 ms 744 KB Output is correct
11 Correct 5 ms 864 KB Output is correct
12 Correct 7 ms 756 KB Output is correct
13 Correct 5 ms 756 KB Output is correct
14 Correct 4 ms 912 KB Output is correct
15 Correct 3 ms 736 KB Output is correct
16 Correct 576 ms 736 KB Output is correct
17 Correct 591 ms 736 KB Output is correct
18 Correct 542 ms 864 KB Output is correct
19 Correct 706 ms 756 KB Output is correct
20 Correct 598 ms 756 KB Output is correct

Subtask #5
0 / 61.0

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