Submission #1120501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120501		vjudge1	KOVANICE (COI15_kovanice)	C++17	100 / 100	949 ms	52036 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
vector<int>g[300005],rg[300005],rco[300005];
int used[300005],scc[300005],ans[300005];
stack<int>s;
int n,m,v;
void dfs(int node)
{
    if(used[node])return;
    used[node]=1;
    for(int i:g[node])if(!used[i])dfs(i);
    s.push(node);
}
void dfs2(int node,int sc)
{
    if(scc[node])return;
    scc[node]=sc;
    for(int go:rg[node])if(!scc[go])dfs2(go,sc);
}
void constructcondensationgraph()
{
    for(int i=1;i<=m;i++)
        for(int go:g[i])
            if(scc[go]!=scc[i])rco[scc[go]].push_back(scc[i]);
}
int longestdag(int node)
{
    if(!used[node])
    {
        int mak=0;
        used[node]=1;
        for(int go:rco[node])
            mak=max(mak,longestdag(go));
        used[node]+=mak;
    }
    return used[node];
}
void answer(int node)
{
    if(!ans[node])
    {
    ans[node]=used[node];
    for(int go:rco[node])
        if(used[go]+1==used[node])answer(go);
    }
}
int main()
{
    cin>>n>>m>>v;
    for(int i=1;i<=v;i++)
    {
        char a;
        int x,y;
        cin>>x>>a>>y;
        //cout<<x<<" "<<a<<" "<<y<<endl;
        if(a=='>')
        {
            g[y].push_back(x);
            rg[x].push_back(y);
        }
        else if(a=='<')
        {
            g[x].push_back(y);
            rg[y].push_back(x);
        }
        else
        {
            g[y].push_back(x);
            rg[x].push_back(y);
            g[x].push_back(y);
            rg[y].push_back(x);
        }
    }
    for(int i=1;i<=m;i++)if(!used[i])dfs(i);
    for(int i=1;i<=m;i++)used[i]=0;
    int sccnum=0;
    while(s.size())
    {
        int node=s.top();
        s.pop();
        if(!scc[node])
        {
            sccnum++;
            dfs2(node,sccnum);
        }
    }
    //for(int i=1;i<=m;i++)cout<<scc[i]<<" ";cout<<endl;
    constructcondensationgraph();
    for(int i=1;i<=m;i++)used[i]=0;
    for(int i=1;i<=m;i++)
        if(!used[scc[i]])
            used[scc[i]]=longestdag(scc[i]);
    //for(int i=1;i<=m;i++)cout<<used[scc[i]]<<' ';cout<<endl;
    for(int i=1;i<=m;i++)
        if(used[scc[i]]==n)answer(scc[i]);
    for(int i=1;i<=m;i++)if(ans[scc[i]])cout<<"K"<<ans[scc[i]]<<endl;else cout<<"?"<<endl;
    return 0;
}

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