Submission #468740

#	Time	Username	Problem	Language	Result	Execution time	Memory
468740		nicolaalexandra	Traffic (CEOI11_tra)	C++14	0 / 100	1844 ms	58868 KiB

tra

#include <bits/stdc++.h>
#define DIM 300010
#define INF 2000000000
using namespace std;

/*vector <int> L[DIM],w[DIM];
set <int> edg[DIM];
bitset <DIM> v[DIM];
pair <int,int> pct[DIM],sol[DIM];
deque <int> c,s;
int viz[DIM],level[DIM],low[DIM],f[DIM],what_comp[DIM],g[DIM];
int n,m,i,j,a,b,x,y,val,idx,nr_comp;

*/

vector <int> L[DIM],inv[DIM],est,vest;
vector <pair<int,int> > d;
int f[DIM],viz[DIM],sol[DIM],dr[DIM],st[DIM];
pair <int,int> pct[DIM];
deque <int> c;
int n,m,a,b,x,y,i,j,val,maxi,mini,poz;

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] = 1;
    if (f[nod] == 2){
        if (pct[nod].second < mini)
            mini = pct[nod].second, poz = nod;
    }
    for (auto vecin : L[nod]){
        if (!viz[vecin])
            dfs (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 (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m>>a>>b;
    for (i=1;i<=n;i++){
        cin>>pct[i].first>>pct[i].second;
        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;
        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++){
        dfs (vest[i]);
        dr[i] = poz;
    }

    memset (viz,0,sizeof viz);
    mini = INF, poz = 0;
    for (int i=0;i<vest.size();i++){
        dfs2 (vest[i]);
        st[i] = poz;
    }

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

    for (i=0;i<vest.size();i++)
        sol[vest[i]] = cautare_binara (est,dr[i]) - cautare_binara (est,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)
        cout<<it.second<<"\n";


    return 0;
}

Compilation message (stderr)

tra.cpp: In function 'int main()':
tra.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i=0;i<vest.size();i++){
      |                  ~^~~~~~~~~~~~
tra.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i=0;i<vest.size();i++){
      |                  ~^~~~~~~~~~~~
tra.cpp:150:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (i=0;i<vest.size();i++)
      |              ~^~~~~~~~~~~~
tra.cpp: In function 'int cautare_binara(std::vector<int>, int)':
tra.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 8
• Subtask 6: 0 / 8
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9