Submission #1225924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225924		PVM_pvm	Stations (IOI20_stations)	C++20	0 / 100	3076 ms	584 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000
int nch[MAXN],sl[MAXN];
vector<int> vv[MAXN];
int sz[MAXN];
void clcsz(int x, int par)
{
    sz[x]=1;
    for (int q=0;q<vv[x].size();q++)
    {
        if (vv[x][q]==par) continue;
        clcsz(vv[x][q],x);
        sz[x]+=sz[ vv[x][q] ];
    }
}
void dfs(int x, int par, int lr, int rr, int dl)
{
    sl[x]=dl;
    if (dl==0)
    {
        nch[x]=lr;
        lr++;
    }
    else
    {
        nch[x]=rr;
        rr--;
    }
    int curl=lr;
    for (int q=0;q<vv[x].size();q++)
    {
        if (vv[x][q]==par) continue;
        dfs(vv[x][q],x,curl,curl+sz[ vv[x][q] ]-1,1-dl);
        curl+=sz[ vv[x][q] ];
    }
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for (int q=0;q<n;q++) vv[q].clear();
	for (int i = 0; i < n-1; i++) {
        vv[ u[i] ].push_back(v[i]);
        vv[ v[i] ].push_back(u[i]);
	}
	clcsz(0,-1);
	dfs(0,-1,0,n-1,0);
	vector<int> labels(n);
	for (int q=0;q<n;q++)
    {
        labels[q]=sl[q]*1000+nch[q];
        //cout<<labels[q]<<" ";
    }
    //cout<<"\n";
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    if (s==0)
    {
        ///tuk nqma roditel i e malko stranna situaciq, zatova she go resha otdelno
        int lst=1;
        int tt=t%1000;
        for (int q=0;q<c.size();q++)
        {
            int curl=lst;
            int curr=c[q]%1000;
            //cout<<curl<<" "<<curr<<" "<<tt<<"\n";
            if (tt>=curl && tt<=curr) return c[q];
            lst=c[q]%1000+1;
        }
        while(true);
        //cout<<"nuleva zaqvka\n";
    }

    ///dai da namerim roditelq
    int prr=-1;
    if (s>=1000)
    {
        prr=0;
    }
    else
    {
        prr=c.size()-1;
    }
    ///dai da namerim rangea
    int lr=-1,rr=-1;
    if (s>=1000)
    {
        rr=s%1000;
        if (c.size()==1) lr=s%1000; ///listo
        else lr=c[1];
    }
    else
    {
        lr=s;
        if (c.size()==1) rr=s; ///listo
        else rr=c[ c.size()-2 ];
    }
    //cout<<"range e "<<lr<<" "<<rr<<" "<<" a tati e "<<c[prr]<<"\n";
    int tt=t%1000;
    if (tt<lr || tt>rr) return c[prr]; ///otivame kym tati
    if (s>=1000)
    {
        int lst=rr-1;
        for (int q=c.size()-1;q>=1;q--)
        {
            int curl=c[q];
            int curr=lst;
            if (tt>=curl && tt<=curr) return c[q];
            lst=c[q]-1;
        }
    }
    else
    {
        int lst=lr+1;
        for (int q=0;q<c.size()-1;q++)
        {
            int curl=lst;
            int curr=c[q]%1000;
            if (tt>=curl && tt<=curr) return c[q];
            lst=c[q]%1000+1;
        }
    }
        while(true);
    ///return c[0];
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61