Submission #236697

#	Time	Username	Problem	Language	Result	Execution time	Memory
236697		Mercenary	Traffic (CEOI11_tra)	C++14	100 / 100	1214 ms	77460 KiB

tra

#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 (stderr)

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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9