Submission #1078673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078673		LmaoLmao	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	4 ms	7516 KiB

oneway

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<ll,5>;

const int N = 1e6;
const int INF = 1e9;

int p[100005];
vector<array<int,3>> bridge;
int timer=0;
int num[100005],low[100005];
vector<ii> adj[100005];
vector<int> adjtree[100005];
vector<ii> edge;
char ans[100005];
map<ii,bool> cb;
int par[100005][1];
int d[100005];  
int pre[100005];  
vector<int> mp[100005];

void dfs(int u,int pre) {
    timer++;
    num[u]=timer;
    low[u]=num[u];
    for(ii v:adj[u]) {
        if(v.first==pre) continue;
        if(!num[v.first] ) {
            dfs(v.first,u);
            low[u]=min(low[u],low[v.first]);
            if(low[v.first]==num[v.first]) {
                bridge.push_back({u,v.first,v.second});
                cb[{u,v.first}]=1;
                cb[{v.first,u}]=1;
            }
        }
        else {
            low[u]=min(low[u],num[v.first]);
        }
    }
    return;
}

int get(int u) {
    if(p[u]<0) return u;
    return p[u]=get(p[u]);
}
void unite(int u,int v) {
    u=get(u);
    v=get(v);
    if(u==v) return;
    if(p[u]>p[v]) swap(u,v);
    p[u]+=p[v];
    p[v]=u;
    return;
}
void tree(int u,int pre) {
    mp[d[u]].push_back(u);
    for(int v:adjtree[u]) {
        v=get(v);
        if(d[v]>0) continue;
        par[v][0]=u;
        d[v]=d[u]+1;
        tree(v,u);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) {
        p[i]=-1;
    }
    for(int i=0;i<m;i++) {
        int x,y;
        cin >> x >> y;
        adj[x].push_back({y,i});
        adj[y].push_back({x,i});
        edge.push_back({x,y});
        ans[i]='X';
    }
    dfs(1,0);
    for(ii e:edge) {
        int u=e.fi;
        int v=e.se; 
        if(cb[{u,v}]==0) {
            unite(u,v);
        }    
    }
    for(array<int,3> e:bridge) {
        int u=e[0];
        int v=e[1]; 
        u=get(u);
        v=get(v);
        adjtree[u].push_back(v);
        adjtree[v].push_back(u);
    }
    for(int i=1;i<=n;i++) {
        int u=get(i);
        if(d[u]>0) continue;
        //cout << u << ' ';
        d[u]=1;
        tree(u,0);
    }
    int k;
    cin >> k;
    for(int i=0;i<k;i++) {
        int x,y;
        cin >> x >> y;
        x=get(x);
        y=get(y);
        pre[x]++;
        pre[y]--;
    }
    for(int i=100000;i>0;i--) {
        for(int u:mp[i]) {
            int v=par[u][0];
            //cout << u << ' ' << v << endl;
            pre[v]+=pre[u];
        }
    }
    for(array<int,3> e:bridge) {
        int u=e[0];
        int v=e[1]; 
        u=get(u);
        v=get(v);
        if(d[u]<d[v]) swap(u,v);
        if(pre[u]>0) {
            if(u==edge[e[2]].first) {
                ans[e[2]]='P';
            }
            else {
                ans[e[2]]='T';
            }
        }
        if(pre[u]<0) {
            if(u==edge[e[2]].first) {
                ans[e[2]]='T';
            }
            else {
                ans[e[2]]='P';
            }
        }
    }
    for(int i=0;i<m;i++) {
        cout << ans[i];
    }
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40