oj.uz

Submission #236697

# Submission time Handle Problem Language Result Execution time Memory
236697 2020-06-02T23:55:36 Z Mercenary Traffic (CEOI11_tra) C++14
100 / 100
 1214 ms 77460 KB 
#include<bits/stdc++.h>

using namespace std;
#define taskname "TEST"
#define pb    push_back
#define mp     make_pair
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 3e5 + 5;

int n , m , A , B;
pair<int,int> a[maxn];
#define x first
#define y second
vector<int> adj[maxn];
vector<int> adj1[maxn];

void enter()
{
    cin >> n >> m >> A >> B;
    for(int i = 1 ; i <= n ; ++i)cin >> a[i].x >> a[i].y;
    for(int i = 1 ; i <= m ; ++i)
    {
        int u , v , k;
        cin >> u >> v >> k;
        adj[u].pb(v);
        adj1[v].pb(u);
        if(k == 2){
            adj[v].pb(u);
            adj1[u].pb(v);
        }
    }
}

bool vis[maxn];
vector<int> st;

void DFS(int u)
{
    vis[u] = 1;
    for(int c : adj[u])
        if(vis[c] == 0)DFS(c);
    st.pb(u);
}

int gr[maxn];
vector<int> mem[maxn];
int nTime = 0;

void DFS1(int u)
{
    gr[u] = nTime;
    for(int c : adj1[u])
        if(gr[c] == 0)
            DFS1(c);
    mem[nTime].pb(u);
}

int Max[maxn] , Min[maxn];

vector<int> vec;

void DFS2(int u)
{
    Min[u] = 1e9 + 1;
    Max[u] = -1;
    vis[u] = 1;
    for(int v : mem[u])
    {
        if(a[v].first == A)
        {
            Max[u] = max(Max[u] , a[v].second);
            Min[u] = min(Min[u] , a[v].second);
            vec.pb(a[v].second);
        }
        for(int c : adj[v])
        {
            if(vis[gr[c]] == 0){
                DFS2(gr[c]);
            }
            Max[u] = max(Max[u] , Max[gr[c]]);
            Min[u] = min(Min[u] , Min[gr[c]]);
        }
    }
}

void solve()
{
    st.reserve(n);
    for(int i = 1 ; i <= n ; ++i)
        if(vis[i] == 0)DFS(i);
    for(int i = n - 1 ;  i >= 0 ; --i)
    {
        if(gr[st[i]] == 0)
        {
            ++nTime;
            DFS1(st[i]);
        }
    }
    fill_n(vis,maxn,0);
    for(int i = 1 ; i <= n ; ++i)
        if(a[i].first == 0 && vis[gr[i]] == 0)DFS2(gr[i]);
    sort(vec.begin(),vec.end());
    vector<pair<int,int>> res;
    for(auto c : vec)debug(c);
    for(int i = 1 ; i <= n ; ++i)
        if(a[i].first == 0){
            res.pb(mp(a[i].second,upper_bound(vec.begin(),vec.end(),Max[gr[i]]) - lower_bound(vec.begin(),vec.end(),Min[gr[i]])));
            debug(i,gr[i],Min[gr[i]],Max[gr[i]]);
        }
    sort(res.begin(),res.end(),greater<ii>());
    for(auto c : res)cout << max(c.second,0) << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r"))
        freopen(taskname".INP", "r",stdin) ,
        freopen(taskname".OUT", "w",stdout);
    enter();
    solve();
}

Compilation message

tra.cpp: In function 'void _dbg(const char*, TH, TA ...)':
tra.cpp:9:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
   ^~~~~
tra.cpp:9:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
                                     ^~~~
tra.cpp: In function 'void solve()':
tra.cpp:118:28: warning: statement has no effect [-Wunused-value]
tra.cpp:15:20:
 #define debug(...) (__VA_ARGS__)
                    ~~~~~~~~~~~~~
tra.cpp:118:28:
     for(auto c : vec)debug(c);
tra.cpp:15:21: note: in definition of macro 'debug'
 #define debug(...) (__VA_ARGS__)
                     ^~~~~~~~~~~
tra.cpp:122:25: warning: left operand of comma operator has no effect [-Wunused-value]
             debug(i,gr[i],Min[gr[i]],Max[gr[i]]);
                         ^
tra.cpp:15:21: note: in definition of macro 'debug'
 #define debug(...) (__VA_ARGS__)
                     ^~~~~~~~~~~
tra.cpp:122:25: warning: right operand of comma operator has no effect [-Wunused-value]
             debug(i,gr[i],Min[gr[i]],Max[gr[i]]);
                     ~~~~^
tra.cpp:15:21: note: in definition of macro 'debug'
 #define debug(...) (__VA_ARGS__)
                     ^~~~~~~~~~~
tra.cpp:122:36: warning: right operand of comma operator has no effect [-Wunused-value]
             debug(i,gr[i],Min[gr[i]],Max[gr[i]]);
                           ~~~~~~~~~^
tra.cpp:15:21: note: in definition of macro 'debug'
 #define debug(...) (__VA_ARGS__)
                     ^~~~~~~~~~~
tra.cpp: In function 'int main()':
tra.cpp:133:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
tra.cpp:133:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21760 KB Output is correct
2 Correct 18 ms 21760 KB Output is correct
3 Correct 17 ms 21760 KB Output is correct
4 Correct 17 ms 21760 KB Output is correct
5 Correct 17 ms 21760 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21760 KB Output is correct
2 Correct 18 ms 21888 KB Output is correct
3 Correct 18 ms 21760 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21760 KB Output is correct
2 Correct 17 ms 21888 KB Output is correct
3 Correct 18 ms 21920 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 22144 KB Output is correct
2 Correct 22 ms 22528 KB Output is correct
3 Correct 21 ms 22272 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24952 KB Output is correct
2 Correct 82 ms 29304 KB Output is correct
3 Correct 47 ms 25336 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 27256 KB Output is correct
2 Correct 96 ms 31096 KB Output is correct
3 Correct 75 ms 28792 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 33012 KB Output is correct
2 Correct 182 ms 38500 KB Output is correct
3 Correct 258 ms 35704 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 34424 KB Output is correct
2 Correct 203 ms 36888 KB Output is correct
3 Correct 322 ms 36216 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 43380 KB Output is correct
2 Correct 347 ms 50756 KB Output is correct
3 Correct 568 ms 49208 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 57208 KB Output is correct
2 Correct 579 ms 66540 KB Output is correct
3 Correct 584 ms 52892 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 66852 KB Output is correct
2 Correct 668 ms 67732 KB Output is correct
3 Correct 1148 ms 66552 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 51320 KB Output is correct
2 Correct 717 ms 71664 KB Output is correct
3 Correct 939 ms 64392 KB Output is correct
4 Correct 1214 ms 77460 KB Output is correct