oj.uz

Submission #468783

# Submission time Handle Problem Language Result Execution time Memory
468783 2021-08-29T15:32:12 Z nicolaalexandra Traffic (CEOI11_tra) C++14
100 / 100
 846 ms 89284 KB 
#include <bits/stdc++.h>
#define DIM 900010
#define DIMBUFF 1000000
#define INF 2000000000
using namespace std;
//FILE *fin = fopen ("date.in","r");
//FILE *fout = fopen ("date.out","w");

FILE *fin = stdin;
FILE *fout = stdout;
vector <int> L[DIM],inv[DIM],est,vest;
vector <pair<int,int> > d;
int f[DIM],viz[DIM],sol[DIM],dr[DIM],st[DIM],what_poz[DIM];
pair <int,int> pct[DIM];
deque <int> c;
int n,m,a,b,x,y,i,j,val,maxi,mini,poz,ok,pos;
char buff[DIMBUFF];

int get_nr(){
    while (!(buff[pos] >= '0' && buff[pos] <= '9')){
        pos++;
        if (pos == DIMBUFF){
            fread (buff,1,DIMBUFF,fin);
            pos = 0;
        }
    }
    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr * 10 + buff[pos] - '0';
        pos++;
        if (pos == DIMBUFF){
            fread (buff,1,DIMBUFF,fin);
            pos = 0;
        }
    }
    return nr;
}

void dfs (int nod){
    viz[nod] = 1;
    if (f[nod] == 2){
        if (pct[nod].second > maxi)
            maxi = pct[nod].second, poz = nod;
    }
    for (auto vecin : L[nod]){
        if (!viz[vecin])
            dfs (vecin);
    }
}

void dfs2 (int nod){
    viz[nod] = val;
    if (f[nod] == 2){
        if (pct[nod].second < mini)
            mini = pct[nod].second, poz = nod;
    }
    for (auto vecin : L[nod]){
        if (!viz[vecin])
            dfs2 (vecin);
    }
}

inline int cmp (int a, int b){
    return pct[a].second < pct[b].second;
}

int cautare_binara (vector<int> v, int x){

    int st = 0, dr = v.size()-1;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (pct[v[mid]].second == pct[x].second)
            return mid;
        if (pct[v[mid]].second < pct[x].second)
            st = mid+1;
        else dr = mid-1;
    }

}

int main (){

    fread (buff,1,DIMBUFF,fin);

    n = get_nr(), m = get_nr(), a = get_nr(), b = get_nr();
    //cin>>n>>m>>a>>b;
    for (i=1;i<=n;i++){
        //cin>>pct[i].first>>pct[i].second;
        pct[i].first = get_nr(), pct[i].second = get_nr();
        if (pct[i].first == 0)
            f[i] = 1; /// vest
        if (pct[i].first == a)
            f[i] = 2; /// est
    }

    for (i=1;i<=m;i++){
        //cin>>x>>y>>val;
        x = get_nr(), y = get_nr(), val = get_nr();
        L[x].push_back(y);
        inv[y].push_back(x);
        if (val == 2){
            L[y].push_back(x);
            inv[x].push_back(y);
        }
    }

    /// pastrez doar nodurile din dreapta care sunt reachable din stanga

    for (i=1;i<=n;i++)
        if (f[i] == 1){
            c.push_back(i);
            viz[i] = 1;
        }

    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        for (auto vecin : L[nod]){
            if (!viz[vecin]){
                viz[vecin] = 1;
                c.push_back(vecin);
            }}}

    for (i=1;i<=n;i++)
        if (f[i] == 2 && viz[i])
            est.push_back(i);

    /// pastrez in stanga doar nodurile care conteaza si din care pot sa ajung in dr

    c.clear();
    memset (viz,0,sizeof viz);
    for (i=1;i<=n;i++)
        if (f[i] == 2){
            c.push_back(i);
            viz[i] = 1;
        }
    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        for (auto vecin : inv[nod]){
            if (!viz[vecin]){
                viz[vecin] = 1;
                c.push_back(vecin);
            }}}

    for (i=1;i<=n;i++)
        if (f[i] == 1 && viz[i])
            vest.push_back(i);


    sort (vest.begin(),vest.end(),cmp);

    memset (viz,0,sizeof viz);
    for (int i=0;i<vest.size();i++){
        maxi = -INF, poz = 0;
        dfs (vest[i]);
        if (poz)
            dr[i] = poz;
        else dr[i] = dr[i-1];
    }

    memset (viz,0,sizeof viz);

    for (int i=vest.size()-1;i>=0;i--){
        mini = INF, poz = 0;
        dfs2 (vest[i]);
        if (poz)
            st[i] = poz;
        else st[i] = st[i+1];
    }

    sort (est.begin(),est.end(),cmp);

    for (i=0;i<est.size();i++)
        what_poz[est[i]] = i;

    for (i=0;i<vest.size();i++)
        sol[vest[i]] = what_poz[dr[i]] - what_poz[st[i]] + 1;

    for (i=1;i<=n;i++)
        if (f[i] == 1)
            d.push_back(make_pair(pct[i].second,sol[i]));

    sort (d.begin(),d.end());
    reverse(d.begin(),d.end());
    for (auto it : d)
        fprintf(fout,"%d\n",it.second);
        //cout<<it.second<<"\n";


    return 0;
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:154:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for (int i=0;i<vest.size();i++){
      |                  ~^~~~~~~~~~~~
tra.cpp:174:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for (i=0;i<est.size();i++)
      |              ~^~~~~~~~~~~
tra.cpp:177:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for (i=0;i<vest.size();i++)
      |              ~^~~~~~~~~~~~
tra.cpp: In function 'int get_nr()':
tra.cpp:23:19: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |             fread (buff,1,DIMBUFF,fin);
      |             ~~~~~~^~~~~~~~~~~~~~~~~~~~
tra.cpp:32:19: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |             fread (buff,1,DIMBUFF,fin);
      |             ~~~~~~^~~~~~~~~~~~~~~~~~~~
tra.cpp: In function 'int cautare_binara(std::vector<int>, int)':
tra.cpp:79:1: warning: control reaches end of non-void function [-Wreturn-type]
   79 | }
      | ^
tra.cpp: In function 'int main()':
tra.cpp:83:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     fread (buff,1,DIMBUFF,fin);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 46028 KB Output is correct
2 Correct 27 ms 46148 KB Output is correct
3 Correct 28 ms 46028 KB Output is correct
4 Correct 27 ms 46156 KB Output is correct
5 Correct 28 ms 46100 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 46156 KB Output is correct
2 Correct 30 ms 46028 KB Output is correct
3 Correct 31 ms 46064 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 46148 KB Output is correct
2 Correct 29 ms 46204 KB Output is correct
3 Correct 28 ms 46152 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 46332 KB Output is correct
2 Correct 30 ms 46700 KB Output is correct
3 Correct 32 ms 46476 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47708 KB Output is correct
2 Correct 62 ms 51416 KB Output is correct
3 Correct 43 ms 48896 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 50112 KB Output is correct
2 Correct 86 ms 52676 KB Output is correct
3 Correct 73 ms 50884 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 52792 KB Output is correct
2 Correct 129 ms 56596 KB Output is correct
3 Correct 177 ms 55384 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 54600 KB Output is correct
2 Correct 128 ms 56308 KB Output is correct
3 Correct 194 ms 55944 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 58692 KB Output is correct
2 Correct 227 ms 62696 KB Output is correct
3 Correct 376 ms 62660 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 65232 KB Output is correct
2 Correct 403 ms 72240 KB Output is correct
3 Correct 448 ms 74032 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 76848 KB Output is correct
2 Correct 416 ms 73896 KB Output is correct
3 Correct 720 ms 89284 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 59200 KB Output is correct
2 Correct 517 ms 76056 KB Output is correct
3 Correct 623 ms 70264 KB Output is correct
4 Correct 846 ms 80556 KB Output is correct