oj.uz

Submission #1120501

# Submission time Handle Problem Language Result Execution time Memory
1120501 2024-11-28T07:58:08 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 949 ms 52036 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21596 KB Output is correct
2 Correct 23 ms 21584 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 31476 KB Output is correct
2 Correct 395 ms 32172 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 24136 KB Output is correct
2 Correct 59 ms 24372 KB Output is correct
3 Correct 48 ms 24212 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 44360 KB Output is correct
2 Correct 949 ms 46920 KB Output is correct
3 Correct 867 ms 46408 KB Output is correct
4 Correct 888 ms 46612 KB Output is correct
5 Correct 805 ms 52036 KB Output is correct