Submission #1084395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084395		vjudge1	KOVANICE (COI15_kovanice)	C++17	60 / 100	2025 ms	40652 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
vector<int>v,top,res;
vector<bool>vis,vis1;
vector<int>g[300001];
int n,k,q;
void dfs(int a,int b)
{
    for(auto i:g[a])
    {
        if(!vis[i]&&i!=b)
        {
            dfs(i,a);
        }
    }
    top.push_back(a);
    vis[a]=1;
}
bool dfs1(int a,int b,int d)
{
      if(d==n)
      {
          vis[a]=1;
          vis1[a]=1;
          res[a]=n;
          return true;
      }
      if(vis[a]==1)
      {
          if(vis1[a]==1&&res[a]==d)
          {
              return true;
          }
          else if(res[a]>=d)
          {
              return false;
          }
      }
      bool check=false;
      res[a]=d;
      vis[a]=true;
      for(auto i:g[a])
      {
          if(i!=b)
          {
              if(dfs1(i,a,d+1))
              {
                  check=true;
              }
          }
      }
      if(check)
      {
          vis1[a]=true;
      }
      return vis1[a];
}
int vfind(int a)
{
    if(v[a]==a)
    {
        return a;
    }
    v[a]=vfind(v[a]);
    return v[a];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    vector<pair<int,int>>vq;
    cin>>n>>k>>q;
    unordered_map<int,int>m;
    for(int i=0;i<k;i++)
    {
        v.push_back(i);
    }
    int sizek=k;
    for(int i=0;i<q;i++)
    {
        int b,c;
        char a;
        cin>>b>>a>>c;
        b--;
        c--;
        if(a=='=')
        {
            vfind(b);
            vfind(c);
            if(v[b]!=v[c])
            {
                sizek--;
                v[v[b]]=v[c];
            }
        }
        else
        {
            vq.push_back({b,c});
        }
    }
    int cnt=0;
    for(int i=0;i<k;i++)
    {
        v[i]=vfind(v[i]);
        if(m.find(v[i])==m.end())
        {
            m.insert({v[i],cnt});
            cnt++;
        }
    }
    vis.resize(cnt);
    vis1.resize(cnt);
    res.resize(cnt);
    for(auto p:vq)
    {
        g[m[v[p.first]]].push_back(m[v[p.second]]);
    }
    for(int i=0;i<cnt;i++)
    {
        if(!vis[i])
        {
            dfs(i,i);
        }
    }
    for(int i=0;i<cnt;i++)
    {
        vis[i]=0;
    }
    for(int i=cnt-1;i>=0;i--)
    {
        if(!vis[top[i]])
        {
            dfs1(top[i],top[i],1);
        }
    }
    for(int i=0;i<k;i++)
    {
        if(vis1[m[v[i]]])
        {
            cout<<"K"<<res[m[v[i]]];
        }
        else
        {
            cout<<"?";
        }
        cout<<"\n";
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 0 / 40