oj.uz

Submission #115553

# Submission time Handle Problem Language Result Execution time Memory
115553 2019-06-08T06:48:51 Z gs14004 Traffic (CEOI11_tra) C++17
100 / 100
 1447 ms 62000 KB 
// remember! no guarantee for connected graph!

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> pi;

vector<int> graph[300005], rev[300005];
vector<int> dfn;
int comp[300005], piv, vis[300005];

vector<int> dag[300005];
pi seg[300005];

int n,m,a,b;
int x[300005], y[300005];
vector<int> endp;
vector<pi> print;

void dfs(int x){
    if(vis[x]) return;
    vis[x] = 1;
    for (int i=0; i<graph[x].size(); i++){
        dfs(graph[x][i]);
    }
    dfn.push_back(x);
}

void dfs2(int x, int p){
    if(vis[x]) return;
    vis[x] = 1;
    comp[x] = p;
    for (int i=0; i<rev[x].size(); i++){
        dfs2(rev[x][i],p);
    }
}

void input(){
    scanf("%d %d %d %d",&n,&m,&a,&b);
    for (int i=1; i<=n; i++) {
        scanf("%d %d",&x[i],&y[i]);
        if(x[i] == 0) print.push_back(pi(y[i],i));
    }
    for (int i=0; i<m; i++) {
        int s,e,x;
        scanf("%d %d %d",&s,&e,&x);
        graph[s].push_back(e);
        rev[e].push_back(s);
        if(x == 2){
            graph[e].push_back(s);
            rev[s].push_back(e);
        }
    }
    for (int i=1; i<=n; i++) {
        if(!vis[i]) dfs(i);
    }
    memset(vis,0,sizeof(vis));
    for (int i=(int)dfn.size()-1; i>=0; i--) {
        if(!vis[dfn[i]]) dfs2(dfn[i],++piv);
    }
    for (int i=1; i<=piv; i++) {
        seg[i] = pi(1e9,-1e9);
    }
}

queue<int> q;

void make_end(){
    memset(vis,0,sizeof(vis));
    for (int i=0; i<print.size(); i++) {
        q.push(print[i].second);
        vis[print[i].second] = 1;
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i=0; i<graph[x].size(); i++) {
            if(!vis[graph[x][i]]){
                q.push(graph[x][i]);
                vis[graph[x][i]] = 1;
            }
        }
    }
    for (int i=1; i<=n; i++) {
        if(x[i] == a && vis[i]){
            endp.push_back(y[i]);
        }
    }
    sort(endp.begin(),endp.end());
}

int main(){
    input();
    make_end();
    sort(print.begin(),print.end());
    for (int i=1; i<=n; i++) {
        int pos = (int)(lower_bound(endp.begin(),endp.end(),y[i]) - endp.begin());
        if(x[i] == a && pos != endp.size() && endp[pos] == y[i]){
            seg[comp[i]].first = min(seg[comp[i]].first,pos);
            seg[comp[i]].second = max(seg[comp[i]].second,pos);
        }
        for (int j=0; j<graph[i].size(); j++) {
            if(comp[i] != comp[graph[i][j]]){
                dag[comp[i]].push_back(comp[graph[i][j]]);
            }
        }
    }
    for (int i=piv; i; i--) {
        for (int j=0; j<dag[i].size(); j++) {
            seg[i].first = min(seg[i].first,seg[dag[i][j]].first);
            seg[i].second = max(seg[i].second,seg[dag[i][j]].second);
        }
    }
    for (int i=(int)print.size()-1; i>=0; i--) {
        int pos = comp[print[i].second];
        printf("%d\n",max(0,seg[pos].second - seg[pos].first + 1));
    }
}

Compilation message

tra.cpp: In function 'void dfs(int)':
tra.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[x].size(); i++){
                   ~^~~~~~~~~~~~~~~~
tra.cpp: In function 'void dfs2(int, int)':
tra.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<rev[x].size(); i++){
                   ~^~~~~~~~~~~~~~
tra.cpp: In function 'void make_end()':
tra.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<print.size(); i++) {
                   ~^~~~~~~~~~~~~
tra.cpp:81:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<graph[x].size(); i++) {
                       ~^~~~~~~~~~~~~~~~
tra.cpp: In function 'int main()':
tra.cpp:102:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(x[i] == a && pos != endp.size() && endp[pos] == y[i]){
                         ~~~~^~~~~~~~~~~~~~
tra.cpp:106:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<graph[i].size(); j++) {
                       ~^~~~~~~~~~~~~~~~
tra.cpp:113:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<dag[i].size(); j++) {
                       ~^~~~~~~~~~~~~~
tra.cpp: In function 'void input()':
tra.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d",&n,&m,&a,&b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x[i],&y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
tra.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&s,&e,&x);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22656 KB Output is correct
2 Correct 21 ms 22656 KB Output is correct
3 Correct 20 ms 22656 KB Output is correct
4 Correct 21 ms 22628 KB Output is correct
5 Correct 20 ms 22656 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22656 KB Output is correct
2 Correct 21 ms 22656 KB Output is correct
3 Correct 21 ms 22656 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22692 KB Output is correct
2 Correct 21 ms 22724 KB Output is correct
3 Correct 20 ms 22656 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 22784 KB Output is correct
2 Correct 29 ms 23232 KB Output is correct
3 Correct 26 ms 23160 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24820 KB Output is correct
2 Correct 101 ms 28928 KB Output is correct
3 Correct 56 ms 25336 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 26168 KB Output is correct
2 Correct 134 ms 28660 KB Output is correct
3 Correct 99 ms 28124 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 30068 KB Output is correct
2 Correct 206 ms 33776 KB Output is correct
3 Correct 330 ms 32392 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 30704 KB Output is correct
2 Correct 247 ms 32752 KB Output is correct
3 Correct 387 ms 32624 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 36288 KB Output is correct
2 Correct 385 ms 41460 KB Output is correct
3 Correct 717 ms 41192 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 52068 KB Output is correct
2 Correct 755 ms 57652 KB Output is correct
3 Correct 874 ms 51284 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1445 ms 57036 KB Output is correct
2 Correct 758 ms 58852 KB Output is correct
3 Correct 1369 ms 52068 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 44480 KB Output is correct
2 Correct 821 ms 62000 KB Output is correct
3 Correct 1095 ms 58112 KB Output is correct
4 Correct 1447 ms 55928 KB Output is correct