Submission #1084295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084295		vjudge1	KOVANICE (COI15_kovanice)	C++17	0 / 100	181 ms	34740 KiB

kovanice

#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);
        }
    }
    for(int i = 0;i < n;i++){
        int j = ind[find(i)];
        if(A[j])cout<<"K"<<A[j]<<'\n';
        else cout<<"?\n";
    }
}

Compilation message (stderr)

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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40