Submission #185354

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
185354	2020-01-11 11:23:17	nicolaalexandra	Railway (BOI17_railway)	C++14	100 / 100	758 ms	131944 KiB

railway

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
#include <bits/stdc++.h>
#define DIM 1000010
using namespace std;
int whatChain[DIM],positionInChain[DIM],chainFatherNode[DIM],Size[DIM],level[DIM];
int viz[DIM],low[DIM],niv[DIM],b[DIM],E[DIM*3],first[DIM],fth[DIM],p[DIM],v[DIM];
pair <int,int> rmq[20][DIM*3];
map <pair<int,int>,int> mch;
vector <int> chains[DIM],L[DIM],sol;
vector <pair<int,int> > a[DIM];
int n,m,k,i,j,nod,nr_chains,x,y,nr,lca,aux,K;
void dfs (int nod, int tata){
    E[++k] = nod;
    first[nod] = k;
    niv[nod] = 1 + niv[tata];
    fth[nod] = tata;
    for (auto vecin:L[nod]){
        if (vecin != tata){
            dfs (vecin,nod);
            E[++k] = nod;
        }}
}
void pre_dfs (int nod, int tata){
    viz[nod] = Size[nod] = 1;
    level[nod] = 1+level[tata];
    int ok = 0;
    for (int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
        if (!viz[vecin]){
            ok = 1;
            pre_dfs (vecin,nod);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

railway.cpp: In function 'void pre_dfs(int, int)':
railway.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<L[nod].size();i++){
                  ~^~~~~~~~~~~~~~
railway.cpp:42:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<L[nod].size();i++){
                      ~^~~~~~~~~~~~~~
railway.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<L[nod].size();i++){
                      ~^~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:169:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<2*chains[i].size();j++)
                      ~^~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'int query_aint(int, int, int, int, int)':
railway.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25