Submission #673284

#	Time	Username	Problem	Language	Result	Execution time	Memory
673284		vjudge1	Stations (IOI20_stations)	C++17	0 / 100	1003 ms	508 KiB

stations

#include <bits/stdc++.h>
//#include "stations.h"
using namespace std;
#define ll long long
#define endl '\n'
#define all(a) a.begin(),a.end()
const int mod = 1e7 + 7;
const int N = 1003;

vector<int> node[N];
int col[N];
int t;
bool vis[N];
void dfs(int i, bool cur){
    vis[i] = 1;
    if (cur) col[i]=t++;
    for (auto it : node[i]){
        if (vis[it]) continue;
        dfs(it,cur^1);
    }
    if (!cur) col[i]=t++;
}
/*
void dfs(int i, int p, bool cur){
    if (cur) col[i]=t++;
    for (auto it : node[i]){
        if (it==p) continue;
        dfs(it,i,cur^1);
    }
    if (!cur) col[i]=t++;
}
*/
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
    for (int i=0;i<int(u.size());i++){
        node[u[i]].push_back(v[i]);
        node[v[i]].push_back(u[i]);
    }
    dfs(0,0);
    bool flag = 0;
    for (int i=0;i<n;i++){
        if (flag && !col[i]) col[i]=1982;
        else if (!col[i]) flag = 1;
        labels[i]=col[i];
    }
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    int flag = 1;// 1 im the max, 0 am the min
    int mx = 0;
    int mn = 1e8;
    if (c.size()==1) return c[0];
    for (auto it : c){
        if (it==t) return it;
        if (it < s) flag = 0;
        mx = max(mx,it);
        mn = min(mn,it);
    }
    if (flag){
        for (int i=int(c.size())-1;i>=1;i--){
            if (c[i] <= t) return c[i];
        }
        return c[0];
    }
    else {
        // am the smallest 
        for (int i=0;i<int(c.size())-1;i++){
            if (c[i] >= t) return c[i];
        }
        return c.back();
    }
}
/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> n >> m;
    for (int i=0;i<m;i++){
        int u,v;
        cin >>u >> v;
        u--;
        v--;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    dfs(0,-1,0);
    cout << find_next_station(3,5,{6,7});
}
*/

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