Submission #37934

#	Time	Username	Problem	Language	Result	Execution time	Memory
37934		patrikpavic2	KOVANICE (COI15_kovanice)	C++14	100 / 100	536 ms	40928 KiB

kovanice

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

#define X first
#define Y second

using namespace std;

typedef long long int llint;
typedef pair < int,int> pii;

const int N = 3e5 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

vector < int > g[N];
vector < int > r[N];
vector < pii > edg;
vector < int > vv;

queue < int > q;

int n,m,v;
int col[N],wh[N],par[N],dp[N][2],in[N];
int x,y;
char c;

int pr(int x){
    return par[x] = ((x == par[x]) ? (x) : (pr(par[x])));
}

void mrg(int x,int y){
    par[pr(x)] = pr(y);
}

int main(){
    scanf("%d%d%d",&n,&m,&v);
    for(int i = 1;i<=m;i++)
        par[i] = i;
    for(int i = 0;i<v;i++){
        scanf("%d%c%d",&x,&c,&y);
        if(c == '=') mrg(x,y);
        if(c == '<') edg.push_back(make_pair(x,y));
        if(c == '>') edg.push_back(make_pair(y,x));
    }
    for(int i = 0;i<edg.size();i++){
        g[pr(edg[i].X)].push_back(pr(edg[i].Y));
        r[pr(edg[i].Y)].push_back(pr(edg[i].X));
    }
    for(int i = 1;i<=m;i++){
        if(!g[i].size() && !r[i].size()) continue;
        sort(g[i].begin(),g[i].end());
        g[i].erase(unique(g[i].begin(),g[i].end()),g[i].end());
        sort(r[i].begin(),r[i].end());
        r[i].erase(unique(r[i].begin(),r[i].end()),r[i].end());
        if(!r[i].size()) q.push(i);
        in[i] = r[i].size();
    }
    while(!q.empty()){
        int x = q.front();q.pop();
        vv.push_back(x);
        for(int i = 0;i<g[x].size();i++){
            in[g[x][i]]--;
            if(!in[g[x][i]])
                q.push(g[x][i]);
        }
    }
    for(int i = 0;i<vv.size();i++){
        int x = vv[i];
        dp[x][0] = 0;
        for(int j = 0;j<r[x].size();j++){
            dp[x][0] = max(dp[x][0], dp[r[x][j]][0] + 1);
        }
    }
    for(int i = vv.size() - 1;i>=0;i--){
        int x = vv[i];
        dp[x][1] = 0;
        for(int j = 0;j<g[x].size();j++){
            dp[x][1] = max(dp[x][1], dp[g[x][j]][1] + 1);
        }
    }
    for(int i = 1;i<=m;i++){
        int rl = pr(i);
        if(dp[rl][0] + dp[rl][1] == n - 1) printf("K%d\n",dp[rl][0] + 1);
        else printf("?\n");
    }
}

Compilation message (stderr)

kovanice.cpp: In function 'int main()':
kovanice.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<edg.size();i++){
                    ^
kovanice.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<g[x].size();i++){
                        ^
kovanice.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<vv.size();i++){
                    ^
kovanice.cpp:73:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<r[x].size();j++){
                        ^
kovanice.cpp:80:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<g[x].size();j++){
                        ^
kovanice.cpp:39:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&v);
                             ^
kovanice.cpp:43:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%c%d",&x,&c,&y);
                                 ^

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