Submission #1284641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284641		d1mk	Traffic (CEOI11_tra)	C++20	0 / 100	663 ms	77844 KiB

tra

/// 407!3 +/ \!<07!\*
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

using pi = pair<int,int>;
using ll = long long;

using vi = vector<int>;

using vpi = vector<pi>;
using vvi = vector<vi>;
using vvpi = vector<vpi>;
using va3 = vector<array<int, 3>>;

#define mp make_pair
#define f first
#define s second

#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
#define er erase
#define ub upper_bound
#define lb lower_bound

// loops
#define FOR(i,a,b) for (ll i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (ll i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 3e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!
const char nl = '\n';

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int n, m, a, b;
vvpi g, rg;
vvi graf;
vpi l, r, cord;
va3 edges;
vi up, dn, ans, vis, used;
int s, tp;

void dfs(int u){
    //cout << u << " ";
    if(cord[u].f == a){
        //cout << u << " " << s << " ";
        if(tp)up[s] = (cord[u].s > cord[up[s]].s ? u : up[s]);
        else  dn[s] = (cord[u].s < cord[dn[s]].s ? u : dn[s]);
    }
    trav(v, graf[u]){
        if(vis[v])continue;
        vis[v] = 1;
        dfs(v);
    }
}

void solve(){
    cin >> n >> m >> a >> b;
    g.rsz(n + 1);
    rg.rsz(n + 1);
    cord.rsz(n + 1);
    F0R(i, n){
        int x, y;
        cin >> x >> y;
        if(x == 0)l.eb(y, i + 1);
        if(x == a)r.eb(y, i + 1);
        cord[i + 1] = {x, y};
    }
    //_print(l, r);
    sor(l);
    sor(r);
    F0R(i, m){
        int u, v, k;
        cin >> u >> v >> k;
        g[u].eb(v, sz(edges));
        rg[v].eb(u, sz(edges));
        if(k == 2){
            edges.pb({u, v, 2});
            g[v].eb(u, sz(edges) - 1);
            rg[u].eb(v, sz(edges) - 1);
        }
        else edges.pb({u, v, 1});
    }
    used.resize(sz(edges));
    vis.resize(n + 1);
    queue<pi> q;
    trav(el, l){
        //cout << el.s << " ";
        q.push({el.s, 0});
        vis[el.s]++;
    }
    while(sz(q)){
        pi u = q.front();
        q.pop();
        trav(el, g[u.f]){
            int v, ind;
            tie(v, ind) = el;
            if(v == u.s)continue;
            used[ind]++;
            if(vis[v] == 1)continue;
            vis[v]++;
            q.push({v, u.f});
        }
    }
    trav(el, r){
        //cout << el.s << " ";
        q.push({el.s, 0});
        vis[el.s] += 2;
    }
    while(sz(q)){
        pi u = q.front();
        q.pop();
        trav(el, rg[u.f]){
            int v, ind;
            tie(v, ind) = el;
            if(v == u.s)continue;
            used[ind] += 2;
            if(vis[v] >= 2)continue;
            vis[v] += 2;
            q.push({v, u.f});
        }
    }
    //_print(used, vis);
    graf.resize(n + 1);
    F0R(i, sz(edges)){
        if(used[i] < 3)continue;
        int u = edges[i][0], v = edges[i][1], k = edges[i][2];
        graf[u].pb(v);
        if(k == 2)graf[v].pb(u);
    }
    int m = sz(l);
    up.resize(m);
    dn.resize(m);
    ans.resize(m);
    vis.clear();
    vis.resize(n + 1);
    tp = 1;
    F0R(i, m){
        if(i == 0)up[i] = r[0].s;
        else up[i] = up[i - 1];
        if(!sz(graf[l[i].s]))continue;
        s = i;
        dfs(l[i].s);
    }
    vis.clear();
    vis.resize(n + 1);
    tp = 0;
    R0F(i, m){
        if(i == m - 1)dn[i] = r.back().s;
        else dn[i] = dn[i + 1];
        if(!sz(graf[l[i].s]))continue;
        s = i;
        dfs(l[i].s);
    }
    //_print(up, dn);
    R0F(i, m){
        if(!sz(graf[l[i].s])){
            cout << 0 << nl;
            continue;
        }
        cout << up[i] - dn[i] + 1 << nl;
    }
}


/*


*/

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t; t = 1;while(t--){
        solve();
    }
    return 0;
}

• 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