oj.uz

Submission #480007

# Submission time Handle Problem Language Result Execution time Memory
480007 2021-10-14T08:55:39 Z stefantaga Stations (IOI20_stations) C++14
0 / 100
 1035 ms 768 KB 
#include "stations.h"
#include <cstdio>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int viz[1505],nr;
vector <int> gr[1505];
void dfs(int x,int tata)
{
    viz[x]=nr;
    nr++;
    for (int i=0;i<gr[x].size();i++)
    {
        if (viz[gr[x][i]]==-1&&gr[x][i]!=tata)
        {
            dfs(gr[x][i],x);
        }
    }
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	for (int i=0;i<n;i++)
    {
        viz[i]=-1;
        gr[i].clear();
    }
	for (int i=0;i<n-1;i++)
    {
        gr[u[i]].push_back(v[i]);
        gr[v[i]].push_back(u[i]);
    }
    nr=0;
    dfs(0,-1);
    for (int i=0;i<n;i++)
    {
        labels[i]=viz[i];
    }
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if (c.size()==1)
    {
        return c[0];
    }
    int i;
    if (s==0)
    {
        for (i=0;i<c.size()-1;i++)
        {
            if (c[i]<=t&&t<c[i+1])
            {
                return c[i];
            }
        }
        return c[c.size()-1];
    }
	else
    {
        if (t<=c[0])
        {
            return c[0];
        }
        for (i=1;i<c.size()-1;i++)
        {
            if (c[i]<=t&&t<c[i+1])
            {
                return c[i];
            }
        }
        return c[c.size()-1];
    }
}
#ifdef HOME
static int max_label = 0;
static int r, n, k, q;
static std::vector<int> u, v, labels, answers;
static std::map<int, int> reverse_labels;
static std::vector<std::vector<int>> adjlist;
static int s, t, w;
static std::vector<int> c;
int ceau[100005];
ifstream f("date.in");
ofstream g("date.out");
int main() {
	f>>r;
	for (int tc = 0; tc < r; tc++) {
		f>>n>>k;
		u.resize(n - 1);
		v.resize(n - 1);
		adjlist.clear();
		adjlist.resize(n);
		for (int i = 0; i < n - 1; i++) {
			f>>u[i]>>v[i];
			adjlist[u[i]].push_back(v[i]);
			adjlist[v[i]].push_back(u[i]);
		}
		labels = label(n, k, u, v);
		if ((int)labels.size() != n) {
			g<<"Wrong number of labels";
			exit(0);
		}
		reverse_labels.clear();
		for (int i = 0; i < n; i++) {
			if (labels[i] < 0 || labels[i] > k) {
				g<<"Labels not in good range";
				exit(0);
			}
			if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
				g<<"Labels not unique";
				exit(0);
			}
			reverse_labels[labels[i]] = i;
			if (labels[i] > max_label) {
				max_label = labels[i];
			}
		}
		f>>q;
		for (int i = 0; i < q; i++) {
			f>>s>>t>>w;
			ceau[i]=w;
			c.clear();
			for (int v : adjlist[s]) {
				c.push_back(labels[v]);
			}
			std::sort(c.begin(), c.end());
			int answer = find_next_station(labels[s], labels[t], c);
			if (!std::binary_search(c.begin(), c.end(), answer)) {
				g<<"Label not found";
				exit(0);
			}
			if (reverse_labels[answer]!=w)
            {
                g<<"NO";
                return 0;
            }
			answers.push_back(reverse_labels[answer]);
		}
	}
	g<<max_label<<'\n';
	int poz=0;
	for (int index : answers) {
		g<<index<<'\n';
		poz++;
	}
	exit(0);
}

#endif // HOME

Compilation message

stations.cpp: In function 'void dfs(int, int)':
stations.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i=0;i<gr[x].size();i++)
      |                  ~^~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (i=0;i<c.size()-1;i++)
      |                  ~^~~~~~~~~~~
stations.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for (i=1;i<c.size()-1;i++)
      |                  ~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1035 ms 656 KB Output is correct
2 Correct 905 ms 528 KB Output is correct
3 Incorrect 658 ms 648 KB Wrong query response.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

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