oj.uz

Submission #691976

# Submission time Handle Problem Language Result Execution time Memory
691976 2023-02-01T04:16:49 Z Quan2003 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 13 ms 23772 KB 
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 5e5 + 5;
int up[21][N + 1];
int dp[N + 1],ds[N + 1];
int a[N + 1];
int n,m,q;
vector<pair<int,int>>tadj[N + 1];
vector<int>adj[N + 1];
char ans[N + 1]; 
int trs,dsz,psz;
vector<pair<int,int>>edges; 
vector<pair<int,int>>bridges; 
int cnt; 
bool vis[N + 1],use[N + 1],brid[N + 1]; 
int st[N + 1],low[N + 1];
int comp[N + 1];
int fa[N + 1];
int find(int u){
     if(u == fa[u]) return u;
     return fa[u] = find(fa[u]);
}
void unite(int u,int v){
     u = find(u); v = find(v);
     if(u == v) return;
     if(comp[u] > comp[v]) swap(u,v); 
     comp[v] += comp[u]; 
     fa[u] = v;
}
void dfs(int u,int p){
    a[u] = low[u] = ++dsz;
    for(int i = 0; i < tadj[u].size(); i++){
        auto x = tadj[u][i];
        int v = x.first;
        if(v == p) continue;
        if(!a[v]){
            use[x.second] = 1;
            dfs(v,u);
            low[u] = min(low[u] , low[v]);
            if(low[v] > a[u]) bridges.push_back({u,v}); 
           else unite(u,v);
        }
        else low[u] = min(a[v] , low[u]);
    }
}
void dfs_calc(int u){
    vis[u] = 1; 
    for(int i = 0; i < adj[u].size(); i++){
        auto v = adj[u][i]; 
        if(vis[v]) continue;
        ds[v] = ds[u] + 1; 
        dfs_calc(v);
        dp[u] += dp[v];
    }
} 
int main(){
     scanf("%d%d",&n,&m);
     for(int i = 1; i <= n; i++) fa[i] = i, comp[i] = 1; 
     for(int i = 0; i < m; i++){
         int u,v; scanf("%d%d",&u,&v);
         tadj[u].push_back({v,i});
         tadj[v].push_back({u,i}); 
         edges.push_back({u,v}); 
     }
     for(int i = 1; i <= n; i++){
          if(!a[i]) dfs(i,0); 
     }
     for(int i = 0; i < bridges.size(); i++){
          int u = bridges[i].first; int v = bridges[i].second;
          adj[fa[u]].push_back(fa[v]);
          adj[fa[v]].push_back(fa[u]);
     }
     for(int i = 1; i <= n; i++) if(!vis[i]) dfs_calc(i); 
     scanf("%d",&q); 
     for(int i = 0; i < q; i++){
          int x,y ; scanf("%d%d",&x,&y); 
          dp[fa[x]]++;
          dp[fa[y]]--;
     }
     for(int i = 0; i < edges.size(); i++){
           int u = edges[i].first; int v = edges[i].second;
           //cout<<fa[u]<<' '<<fa[v]<<endl; 
           if(fa[u] == fa[v]) cout<<'B'; 
           else{
                u = fa[u]; v = fa[v];
                if(ds[u] > ds[v]){
                      if(dp[u] > 0) cout<<'R';
                      else if(dp[u] == 0) cout<<'B'; 
                      else cout<<'L'; 
                }
                if(ds[u] < ds[v]){
                      if(dp[v] < 0) cout<<'L'; 
                      else if(dp[v] == 0) cout<<'B'; 
                      else cout<<'R'; 
                }
           }
     }
     return 0; 
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0; i < tadj[u].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs_calc(int)':
oneway.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < adj[u].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |      for(int i = 0; i < bridges.size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~
oneway.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |      for(int i = 0; i < edges.size(); i++){
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp:60:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |      scanf("%d%d",&n,&m);
      |      ~~~~~^~~~~~~~~~~~~~
oneway.cpp:63:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |          int u,v; scanf("%d%d",&u,&v);
      |                   ~~~~~^~~~~~~~~~~~~~
oneway.cpp:77:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |      scanf("%d",&q);
      |      ~~~~~^~~~~~~~~
oneway.cpp:79:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |           int x,y ; scanf("%d%d",&x,&y);
      |                     ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23772 KB Output isn't correct
2 Halted 0 ms 0 KB -