답안 #1098839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098839	2024-10-10T08:17:26 Z	AliHasanli	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	668 ms	51380 KB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;
vector< pair < char,pair < int,int > > > edges;
vector<int>g[500001],g2[500001];
int vst[500001];
void dfs(int node,int p,int col)
{
    vst[node]=col;
    for(int go:g[node])
        if(go!=p && vst[go]==0)
            dfs(go,node,col);
}
bool selected[500001];
int main()
{
    int v,e,comp=0;
    cin>>v>>e;
    while(e--)
    {
        char c;
        int a,b;
        cin>>a>>b>>c;
        edges.push_back({c,{a,b}});
    }
    //sort(edges.begin(),edges.end());
    for(int i=edges.size()-1;i>=0;i--)
    {
        if(edges[i].first=='T')
        {
            g[edges[i].second.first].push_back(edges[i].second.second);
            g[edges[i].second.second].push_back(edges[i].second.first);
        }
    }
    for(int i=1;i<=v;i++)
    {
        if(vst[i]==0)dfs(i,0,comp+1),
        comp++;
    }
    //cout<<"comp: "<<comp<<endl;
    //for(int i=1;i<=v;i++)cout<<visit[i]<<" ";cout<<endl;
    int cav=0;
    /*
    for(int i=1;i<=v;i++)
        for(int n:g[i])
            if(visit[i]!=visit[n])g2[i].push_back(n),g2[n].push_back(i);
    */
    for(int i=0;i<edges.size();i++)
        if(edges[i].first=='A')
            g2[vst[edges[i].second.first]].push_back(vst[edges[i].second.second]),g2[vst[edges[i].second.second]].push_back(vst[edges[i].second.first]);
    for(int i=1;i<=v;i++)
    {
        int ini=comp-1;
        for(int go:g2[vst[i]])
        {
            if(vst[i]!=go && selected[go]==0)
            {
                ini--;
                selected[go]=1;
            }
        }
        //cout<<"i: "<<i<<" ini: "<<ini<<endl;
        if(ini==0)cav++;
        for(int go:g2[vst[i]])
            selected[go]=0;
    }
    cout<<cav;
    return 0;
}

Compilation message

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<char, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<edges.size();i++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	299 ms	51380 KB	Output is correct
2	Correct	11 ms	23896 KB	Output is correct
3	Correct	12 ms	23896 KB	Output is correct
4	Correct	12 ms	25692 KB	Output is correct
5	Correct	11 ms	23900 KB	Output is correct
6	Correct	94 ms	31240 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	25692 KB	Output is correct
2	Correct	11 ms	23900 KB	Output is correct
3	Correct	11 ms	23900 KB	Output is correct
4	Correct	10 ms	23808 KB	Output is correct
5	Correct	12 ms	24156 KB	Output is correct
6	Correct	152 ms	36388 KB	Output is correct
7	Correct	256 ms	51168 KB	Output is correct
8	Correct	19 ms	24856 KB	Output is correct
9	Correct	24 ms	25212 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23896 KB	Output is correct
2	Correct	12 ms	23896 KB	Output is correct
3	Correct	11 ms	23900 KB	Output is correct
4	Correct	10 ms	23808 KB	Output is correct
5	Correct	12 ms	24156 KB	Output is correct
6	Correct	11 ms	23896 KB	Output is correct
7	Correct	12 ms	23900 KB	Output is correct
8	Correct	10 ms	23896 KB	Output is correct
9	Correct	13 ms	23900 KB	Output is correct
10	Correct	15 ms	24196 KB	Output is correct
11	Correct	13 ms	24064 KB	Output is correct
12	Correct	11 ms	23900 KB	Output is correct
13	Correct	11 ms	23836 KB	Output is correct
14	Correct	15 ms	24196 KB	Output is correct
15	Correct	11 ms	23900 KB	Output is correct
16	Correct	11 ms	23964 KB	Output is correct
17	Correct	12 ms	23896 KB	Output is correct
18	Correct	12 ms	23820 KB	Output is correct
19	Correct	12 ms	23900 KB	Output is correct
20	Correct	14 ms	23900 KB	Output is correct

Subtask #4
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23896 KB	Output is correct
2	Correct	12 ms	23900 KB	Output is correct
3	Correct	10 ms	23896 KB	Output is correct
4	Correct	13 ms	23900 KB	Output is correct
5	Correct	15 ms	24196 KB	Output is correct
6	Correct	13 ms	24064 KB	Output is correct
7	Correct	11 ms	23900 KB	Output is correct
8	Correct	11 ms	23836 KB	Output is correct
9	Correct	15 ms	24196 KB	Output is correct
10	Correct	11 ms	23900 KB	Output is correct
11	Correct	11 ms	23964 KB	Output is correct
12	Correct	12 ms	23896 KB	Output is correct
13	Correct	12 ms	23820 KB	Output is correct
14	Correct	12 ms	23900 KB	Output is correct
15	Correct	14 ms	23900 KB	Output is correct
16	Correct	11 ms	23896 KB	Output is correct
17	Correct	12 ms	23896 KB	Output is correct
18	Correct	11 ms	23900 KB	Output is correct
19	Correct	10 ms	23808 KB	Output is correct
20	Correct	12 ms	24156 KB	Output is correct
21	Correct	11 ms	23900 KB	Output is correct
22	Correct	19 ms	24856 KB	Output is correct
23	Correct	24 ms	25212 KB	Output is correct
24	Correct	94 ms	31240 KB	Output is correct
25	Correct	24 ms	24912 KB	Output is correct
26	Correct	189 ms	37652 KB	Output is correct
27	Correct	71 ms	28864 KB	Output is correct
28	Correct	84 ms	30656 KB	Output is correct
29	Correct	52 ms	27848 KB	Output is correct
30	Correct	118 ms	30660 KB	Output is correct

Subtask #5
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23896 KB	Output is correct
2	Correct	12 ms	23900 KB	Output is correct
3	Correct	10 ms	23896 KB	Output is correct
4	Correct	13 ms	23900 KB	Output is correct
5	Correct	15 ms	24196 KB	Output is correct
6	Correct	13 ms	24064 KB	Output is correct
7	Correct	11 ms	23900 KB	Output is correct
8	Correct	11 ms	23836 KB	Output is correct
9	Correct	15 ms	24196 KB	Output is correct
10	Correct	11 ms	23900 KB	Output is correct
11	Correct	11 ms	23964 KB	Output is correct
12	Correct	12 ms	23896 KB	Output is correct
13	Correct	12 ms	23820 KB	Output is correct
14	Correct	12 ms	23900 KB	Output is correct
15	Correct	14 ms	23900 KB	Output is correct
16	Correct	24 ms	24912 KB	Output is correct
17	Correct	189 ms	37652 KB	Output is correct
18	Correct	71 ms	28864 KB	Output is correct
19	Correct	84 ms	30656 KB	Output is correct
20	Correct	52 ms	27848 KB	Output is correct
21	Correct	118 ms	30660 KB	Output is correct
22	Correct	299 ms	51380 KB	Output is correct
23	Correct	11 ms	23896 KB	Output is correct
24	Correct	12 ms	23896 KB	Output is correct
25	Correct	12 ms	25692 KB	Output is correct
26	Correct	11 ms	23900 KB	Output is correct
27	Correct	10 ms	23808 KB	Output is correct
28	Correct	12 ms	24156 KB	Output is correct
29	Correct	11 ms	23900 KB	Output is correct
30	Correct	152 ms	36388 KB	Output is correct
31	Correct	256 ms	51168 KB	Output is correct
32	Correct	19 ms	24856 KB	Output is correct
33	Correct	24 ms	25212 KB	Output is correct
34	Correct	94 ms	31240 KB	Output is correct
35	Correct	74 ms	26828 KB	Output is correct
36	Correct	668 ms	42184 KB	Output is correct
37	Correct	137 ms	36480 KB	Output is correct

답안 #1098839

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 6.0 / 6.0

Subtask #3 30.0 / 30.0

Subtask #4 35.0 / 35.0

Subtask #5 19.0 / 19.0

Subtask #1
10.0 / 10.0

Subtask #2
6.0 / 6.0

Subtask #3
30.0 / 30.0

Subtask #4
35.0 / 35.0

Subtask #5
19.0 / 19.0