oj.uz

Submission #1084290

# Submission time Handle Problem Language Result Execution time Memory
1084290 2024-09-05T18:38:33 Z vjudge1 KOVANICE (COI15_kovanice) C++17
0 / 100
 195 ms 48312 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array

const int LOG = 20;
const int MOD = 1e9 + 7;
const int INF = 1e18;

const int N = 3e5 + 20;

int p[N];
int find(int x){
    if(p[x] == x)return x;
    return p[x] = find(p[x]);
}

void join(int a,int b){
   // cout<<a + 1<<" "<<b + 1<<'\n';
    a = find(a);
    b = find(b);
    p[a] = b;
}

int ind[N];
vector<vector<int> > G;
vector<int> g[N];
int in[N];
bitset<N> vis;
vector<int> path;
int k;
int A[N];
void dfs(int x){
    //cout<<x + 1<<endl;
    path.push_back(x);
    vis[x] = 1;
    if(path.size() == k){
        for(int i = 0;i < k;i++)A[path[i]] = k - i;
    }
    for(auto u: g[x]){
        if(!vis[u])dfs(u);
    }
    path.pop_back();
}

signed main() {
    iota(p, p + N, 0);
    int  n, m;
    cin>>k>>n>>m;
    vector<ar<int, 2> > e;
    while(m--){
        int u, v;
        char c;
        cin>>u;
        c = getchar();
        cin>>v;
        --u, --v;
        //cout<<u<<" "<<c<<" "<<v<<'\n';
        if(c == '=')join(u, v);
        else if(c == '>')e.push_back({u, v});
        else e.push_back({v, u});
    }   
    int T = 0;
    for(int i = 0;i < n;i++){
        if(find(i) == i)ind[i] = T++;
    }
    G.resize(T);
    for(int i = 0;i < n;i++)G[ind[find(i)]].push_back(i);
    for(auto [u, v]: e){
        u = ind[find(u)], v = ind[find(v)];
        //cout<<u<<" "<<v<<endl;
        in[v]++;
        g[u].push_back(v);
    }
    for(int i = 0;i < T;i++){
        if(!in[i]){
            path.clear();
            dfs(i);
        }
    }
    string ans[n];
    for(int i = 0;i < T;i++){
        for(auto u: G[i]){
            //cout<<u + 1<<" ";
            if(A[i])ans[u] = "K" + to_string(A[i]);
            else ans[u] = "?";
        }
        //cout<<endl;
    }
    for(int i = 0;i < n;i++)cout<<ans[i]<<'\n';
}

Compilation message

kovanice.cpp: In function 'void dfs(long long int)':
kovanice.cpp:38:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |     if(path.size() == k){
      |        ~~~~~~~~~~~~^~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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