Submission #45293

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
45293	2018-04-12 15:39:48	bugmenot111	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	386 ms	126696 KiB

oneway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
if an edge is not a bridge it can be oriented either way;
the orientation of the bridges is uniquely determined;
let's call the input pairs "required pairs";
for each bridge B:
if there is no required pair with a node from the first component of the graph and the second component of the graph:
B can be oriented either way
otherwise: orient B the same way as the required pair from component A to component B
obviously, there cannot be two required pairs with different orientations because there can be no solution!
Algorithm: 
  Build "bridge tree" T of G
  For every pair going from comp(u) to comp(v) in T:
    orient all edges from comp(u) to LCA(comp(u), comp(v)) upwards
    orient all edges from LCA(comp(u), comp(v)) to comp(v) downwards
  The loop can be optimized by using a version of the difference array on the tree.
*/
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <queue>
#define MAXN 100100
typedef std::vector< std::pair<int, int> > edge_list;
typedef std::vector< std::vector<int> > graph;
typedef std::vector< std::vector< std::pair<int, int> > > labeled_edge_graph;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

oneway.cpp: In function 'std::vector<int> offline_lca(int, const edge_list&)':
oneway.cpp:143:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < queries.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'std::__cxx11::string solve(int, int, int, const edge_list&, const edge_list&)':
oneway.cpp:186:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p2.size(); i++) {
                 ~~^~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:200:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:205:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:208:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &p);
  ~~~~~^~~~~~~~~~
oneway.cpp:213:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40